CareerCup

We can use stack....

#include<iostream.h>
#include<conio.h>

int main() {
char input[50]="";
int count=0;;
cout<<"\nEnter the string : ";
cin>>input;
char *p=input;
int i=0;
while(p[i]!='\0')
{
if(p[i+1]==p[i]) {
count++;
char *q=&p[i];
while(*(q+2)!='\0') {
*q=*(q+2);
q++;
}
*q='\0';
i=0;
}
else
i++;
}
cout<<"\nfinally we have : "<<input<<"\nMaximum couples : "<<count;
getch();
return 0;
}

#include<stdio.h>
#include<stack>
#include<string.h>
using namespace std;
int main(){
    char input[]="YRGGRRGGRY";
    stack<int> s;
    int count=0;
    int len = strlen(input);
   for(int i=0;i<len;i++){
           if(s.empty()){
                s.push(input[i]);                       
           }else if(s.top() == input[i]){
                 s.pop();
                 count++;      
           }else{
                 s.push(input[i]);
           }      
    }
    printf("counter is %d",count);
    
return 0;    
}

public static int maxPairs(char[] A) {
        if(A==null) {
            return 0;
        }
        int count = 0;
        Stack<Character> st = new Stack<Character>();
        for (int i = 0; i < A.length; i++) {
            if(st.isEmpty()) {
                st.push(A[i]);
            } else if(st.peek()==A[i]) {
                count++;
                st.pop();
            } else {
                st.push(A[i]);
            }
        }
        return count;
    }

top = 0 ;
a[] = //the character array ...

for (i=1;i<size;i++)
{
if(a[top] == a[i])
{
top = top - 1;
count++;
}

else
{
top = top+1;
}
}

It can be done simply like this 0(n) but any one having more optimised solution than o(n) ???

I think with divide and conquer approach we can do it in o(log n ) timing . correct me if i am wrong ..


thanks..

I was asked this question in the Groupon Interview. I told him the solution using stack but he asked me to find a solution with O(1) space complexity, which I couldn't. does anyone know how to solve this without using stack or brute force?

In the above question,the number of pairs can be given as (n-1)/2 if n is odd and n/2 if n is even where n is the length of longest palindromic substring.
This can be done in O(1) space complexity by recursive approach.
int lps(char *seq, int i, int j)
{
// Base Case 1: If there is only 1 character
if (i == j)
return 1;

// Base Case 2: If there are only 2 characters and both are same
if (seq[i] == seq[j] && i + 1 == j)
return 2;

// If the first and last characters match
if (seq[i] == seq[j])
return lps (seq, i+1, j-1) + 2;

// If the first and last characters do not match
return max( lps(seq, i, j-1), lps(seq, i+1, j) );
}

I tried to write following...kindly update in case of any gap/error.

void removeSequence(char **strOrg){
char *str = *strOrg;
int p = 0,q = 0;

while(*(str+p) && *(str+p+1)){
if(*(str+p) != *(str+p+1)){
*(str+q) = *(str+p);
q++;
}
p++;
}
}

time complexity: O(N)
space: O(1)

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
	int arr[15] = {1,2,2,5,4,6,6,4,5,3,3,2,1,1,2};
	int lastInd = 0, compInd = 1;
	int numCpls = 0;
	for(int ind = 1; ind < 15; ind++) {
		if(compInd != ind)
			arr[compInd] = arr[ind];
		if(arr[lastInd] == arr[compInd]) {
			cout << arr[lastInd] <<endl;
			compInd = max(0,lastInd);
			lastInd = max(0,lastInd - 1);
			numCpls++;
		} else {
			compInd++;
			lastInd++;
		}
	}
	cout << "numCpls = "<< numCpls<<endl;

	return 0;
}

public enum Color {
	R,
	G,
	B
};
int NumberOfPairs(Color[] input) {
	int counter = 0;
	for (int top = 0, current = 1; current < input.Length;) {
		if (input[top] == input[current]) {
			//remove pair
			top--;
			current++;
			counter++;
		} else {
			top = current;
			current++;
		}
	}

	return counter;
}

def max_sequence(color_arr)
  found_pair = 0
  new_sequences = []
  (0..color_arr.count-1).each do |c|
    if color_arr[c] == color_arr[c+1]
      found_pair = 1
      end_of_arr = c+1 == color_arr.count ? [] : color_arr[c+2..color_arr.count-1]
      start_of_arr = c == 0 ? [] : color_arr[0..c-1]
      new_sequences << start_of_arr + end_of_arr
    end
  end

  if new_sequences.any?{ |s| !s.empty? }
    return new_sequences.map{ |s| max_sequence(s) }.sort.max + found_pair
  else
    return found_pair
  end
end

We can use stack to solve this problem.
Keep adding elements on the stack till the top of the stack is different then the currently added element. If they are the same remove the top and increment counter. For your example.
1) Add Y, R, G to the stack, next element is G so remove G and increment counter = 1;
2) Stack is Y,R - next is also R so remove the top, counter = 2;
3) Stack is Y, - next is R so add it.
5) Stack is Y R - add G
6) Stack is Y R G - next is also G so remove G, counter = 3
7) Stack is Y R - next is also R so remove the top, counter = 4
8) Stack is Y - the last element is Y, counter = 5
9) Stack is empty.