Facebook Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
24
of 26 vote

Count the number of occurences of each letter in the input string [numA, numB, numC]

If two of these counts are 0, then return string.length

Else if (all counts are even) or (all counts are odd), then return 2

Else, then return 1

- NaiveCoder February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

it seems not work for the following case:
aaaabbbb - > aaacbbb->aabbbb->acbbb->bbbb

- XILI February 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey it works for your case:

aaaabbbb -> aaacbbb -> aaaabb -> aaacb -> aabb -> acb -> bb

so the length is 2

- Bernie February 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you explain your logic?

- Anonymous February 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you explain your logic? how you arrived at this ?

- Anonymous February 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

what about aaa?

- Anonymous March 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I want to know why?

- milo April 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It might works when 3 different letters are given, what if we input more letters like abcddcca

- xiaojian@buffalo.edu April 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Use math induction:
1. if you have case of length 3
if all the same then 3
if all different then 1 (i.e. odd counts)
other cases 2
2. Lemma: If string of length N > 3 consist of non same char it always can be reduced to the length N - 1. (prove is simple)
3. Lemma: If string is N > 3 and consist of non same char during reduction to N-1 it may be represented as a string of non the same chars (reader can prove it too as it's not too hard)
4. Lemma: during reduction from N to N-1 (N > 3) if number of chars been all odd then it will become even and reverse. This is super easy to prove.

Now if you take all this lemmas you can easy to see a logic why it works. First you can always reduce a chain of non same chars up to the string with 3 chars, secondary during reduction you'll end up with odd count if you start count have been even or odd.

- agamemnum September 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

it wont work.
As your alg, aaabbb and aacbb should return different values.
however, they are actually the same string...
try aaabbb, it should return 1 but you algorithm return 2

- nanny October 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

aacbb->aaab->aac->ab->c so it should return 1
aaabbb should return 1 and he does return 1. please check your work over before commenting :)

- hello November 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

#include<iostream>
#include<string>
using namespace std;
bool isequal(string s)
{
	int i=0;
	while(i<s.length()-1)
	{
		if(s[i]!=s[i+1])
		{
			return false;
		}
		i++;
	}
	return true;
}

char cnot(char r,char s)
{
	if(r=='a'&&s=='b')
	{
		return 'c';
	}
	else if(r=='a'&&s=='c')
	{
		return 'b';
	}
	else if(r=='b'&&s=='a')
	{
		return 'c';
	}
	else if(r=='b'&&s=='c')
	{
		return 'a';
	}
	else if(r=='c'&&s=='a')
	{
		return 'b';
	}
	else if(r=='c'&&s=='b')
	{
		return 'a';
	}
}

int length(string s)
{
	int i,n;
	while(!isequal(s))
	{
		n=s.length();
		i=0;
		while(i<n-1)
		{
			if(s[i]!=s[i+1])
			{
				s[i]=cnot(s[i],s[i+1]);
				s=s.substr(0,i+1)+s.substr(i+2);
				n=s.length();
			}
			else
			{
				i++;
			}
		}
	}
	return s.length();
}
int main()
{
	int t,*a;
	string *s;
	cin>>t;
	s=new string[t];
	for(int i=0;i<t;i++)
	{
		cin>>s[i];
	}
	a=new int[t];
	for(int i=0;i<t;i++)
	{
		a[i]=length(s[i]);
	}
	for(int i=0;i<t;i++)
	{
		cout<<a[i]<<"\n";
	}
	return 0;
}

hope this code will be useful...

- chaitanya July 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
6
of 10 vote

i think you shouldn't post those skill tests..
those are not interview questions.

- shaw February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

Ishant, you are correct (though there's still something missing ...). So let me list all possible cases:

(1) String contains only one kind of characters, or more precisely, the string contains k identical characters and nothing else. Clearly, no reduction is poosible and the minimum length is k.

(2) String contains 2 or 3 kinds of characters. Then if all the counts are even or all the counts are odd, the minimum string possible has length 2, otherwise we can reduce it to 1.

Proof (of 2):
With every reduction, the count of 2 characters decreases by 1, and the count of the third character increases by 1. So if all counts are even before reduction, all counts will be odd after reduction, and if allcounts are odd before, they will all be even after. So, for such strings, the shortest possible string we can get is (0, 0, 2) or (cc) or (bb) or (aa). All even counts. This proves that we can't do any better than (0, 0, 2).
Now, are we guaranteed that we can always get to (0,0,2) for the all-odd, all-even strings and to (0,0,1) for the other strings? YES! We just have to be smart about which pairs we reduce. For example, if our string is aaaaaaabc we can either reduce ab or bc. Reducing bc would mean no more reduction so we don't want to do that! So the algorithm to reach minimum string is this -- always reduce a pair that contains a character with maximum count. It does not matter which pair, just that the max count character be reduced. This will eventually result in a string of length 1 or 2 depending on the initial counts.

- czpete425 November 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

could you please give a proof for the part - "So, for ***such strings***, the shortest possible string we can get is (0, 0, 2) or (cc) or (bb) or (aa). "
***such strings*** -- Strings containing 2 or 3 kinds of characters and all the counts are even or all the counts are odd

- confused November 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not sure what you mean ...
The first part of the proof says that for string with all odd counts or all even counts we cannot get any better than (0,0,2). Why, because each reduction brings us from all even to all odd or from all odd to all even. The shortest possible string with all even is (0,0,0) but that cannot be achieved by any reduction, so the next all-even shortest string is (0,0,2). The shortest possible all-odd string is (1,1,1) but that is (a) longer than (0,0,2) and (b) can be reduced to (0,0,2) by one reduction. Note that (0,0,1) is neither all-odd nor all-even so all-odd/all-even strings cannot be reduced to that. Anyway, the first part of the proof is that we cannot do any better than (0,0,2).
The second part of the proof is trying to prove the fact that (using smart reduction) we can indeed make it all the way to (0,0,2) for all-even/all-odd strings, and all the way to (0,0,1) for all the other strings as long the string we are starting from contains 2 or 3 different kinds of characters.

Let me give you an example:
all-odd string (3,1,1): (aaabc)->aacc->abc->cc
regular string (4,1,1): (aabaac)->acaac->baac->cac->bc->a

Hopefully this made it clear :-)

- czpete425 November 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

hey, i think this is not correct. i have seen instances when all the occurances are equal and odd, then it reduces to 1 char. the 2nd last comment is right in this thread.

- radhika December 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Give me just one such instance ... Anybody can say "I have seen ...".

I proved that it's mathematically imposible. If you think the proof is not correct, show me what exactly is wrong or give me a specific counter-example. Otherwise we are wasting time here.

Man I always regret posting to this site ...

- czpete425 December 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

There is a counter-example
"abababab"--> "bb"; length = 2
but
"ababababab"-->"c"; length = 1

- hanks December 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please explain the actual algo behind the reduction , not just on the basis of count/

- Mohan December 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

none of them working correctly.

try for this input abccaccba

solution should be "b"

but they are giving wrong solution.

- skg March 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

none of them working correctly.

try for this input "abccaccba"
solution should be "b"
but they are showing wrong output

- skg March 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

But, abc only reduces to 2

- moh November 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

must depend on how many 'a', 'b' and 'c' the input has; seems with equal number of 'a', 'b' and 'c' the min is 2, otherwise 1. if you just look at the numbers (4,3,5) the way to the min must be through keeping the three counts as close as possible.

4,3,5->3,4,4->4,3,3->3,2,4->2,3,3->3,2,2->2,1,3->1,2,2->2,1,1->1,0,2->0,1,1->1,0,0

3,3,3->2,2,4->1,3,3->2,2,2->1,1,3->2,0,2->1,1,1->0,0,2

waiting for counter examples, thanks

- aaa November 11, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

For aabbccc, its 1, but min consecutive is 2. aabbccc to aabacc to aabbc to acbc to bbc to ba to c.
Better is to look at proof rather than counter example.

- Anonymous November 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what do you mean by min consecutive is 2? thnx

aabbccc
2,2,3->3,1,2->2,2,1->1,1,2->0,2,1->1,1,0->0,0,1

- aaa November 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think you might be correct.

- Andy November 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Well it appears to be that it is going to be either 1 or 2 but with a b c as unequal also the min value will come to 2 for e.g. try acbcc -> aacc -> abc -> cc

- ishantagarwal1986 November 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

1,1,3 - 2,0,2 - 1,1,1 - 0,0,2
thnx

- aaa November 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

For aabbccc
===========
can be 3 or 1, depends on how we solve it
case 1
======
aabbccc ->acbccc->bbccc->bacc->ccc
case 2
======
aabbccc ->acbccc->bbccc->bacc->bbc->ba->c

Pleae correct if anything is not correct.

- him November 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If i, j, k are the number of occurrences of a, b, c respectively where i, j, k >= 1
and if b,a,a,c is a possible combination then the answer is '1'.
Eg.
b,a,a,c can be converted to (b,a),(a,c) => c,b => a

- Mukesh Kumar November 11, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thats perfect !!!

- ayanvit November 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

If either all characters are present odd no of times or all are present even number of times, in tht case the result will be 2 and in any other case the result will be 1. Please suggest a case where this does not hold true.

- ishantagarwal1986 November 12, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ishant , pretty much correct but if we have chars appears different counts the it will also come to count as 2 ,keep it up :)

- WgpShashank December 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes u r right, if given is ab or ac or bc in tht case too it will be 1. looks like what i wrote is true for strings greater or equal to of length 3

- ishantagarwal1986 December 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

aaaaaa

answer will be 6 :P

- Ashu January 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

ishant , your answer is incomplete . if its not I have to give you so easy counter example

- friday November 12, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# of consecutive characters besides matters.
E.G. aaaab, the # of a is even => absorbed to one b.
aaab, the # of a is odd => absorbed to c, a different char other than a and b.

#include <iostream>
#include <string>
using namespace std;

int absorbstr(string str)
{
if (str.empty()) return 0;
if (str.size()==1) return 1;
if (str.size()==2) return str[0]==str[1]?2:1;

int num = 0;
for (size_t ix = 0; ix!=str.size()-1; ++ix)
if(str[ix]!=str[ix+1]) num = ix;
int last_size = str.size()-1-num;

int count = 1;

for (size_t ix = 0; ix!=str.size()-1; ++ix)
{
if (str[ix]==str[ix+1]) ++count;
else {
if( ix==num ) {
if(!(count%2) && !(last_size%2))
return count<last_size?count:last_size;
else return 1;
}
if( count%2 ) str[ix+1] = str[ix]^str[ix+1]^'a'^'b'^'c';
count = 1;
}
}
return count;
}

int main(int argc, char* argv[])
{
cout << argv[1] << "=>" << absorbstr(argv[1]) << endl;
return 1;
}

- biostanley November 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

case 1: only 1 char: understood
case 2: any 2 or 3 char
if count of any char is odd then min possible length = 1, else if all chars count is even min possiblee length is 2. since in case of even eventually you will left with 2 similar chars which will not be able to generate 3rd char.

- Anonymous November 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Well if you have string: abb then you can reduce it to cb and then to just a. The answer therefore is 1

- ashishkaila@hotmail.com November 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

stackoverflow . com/ questions/ 8551519/ string-reduction-programming-contest-solution-needed/ 8997695#8997695

- smffap January 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//a really dumb solution using DP
public class Test {
	String needTest = "cab";
	int sum = 'a' + 'b' + 'c';
	Test()
	{
		System.out.println(testString(needTest));
	}
	int testString(String s)
	{
		int min = s.length();
		if(min == 1)
		{
			return 1;
		}else if(min == 2)
		{
			if(s.charAt(0) == s.charAt(1))
			{
				return 2;
			}else
			{
				return 1;
			}
		}
		
		StringBuffer sb = new StringBuffer();
		for(int i= 1; i<s.length() ; i++)
		{
			if(s.charAt(i) != s.charAt(i-1))
			{
				sb = new StringBuffer();
				sb.append(s.substring(0, i-1));
				sb.append((char)(sum - s.charAt(i) - s.charAt(i-1)));
				if(i<s.length()-1)
				{
					sb.append(s.substring(i+1));
				}
				int temp = testString(sb.toString());
				if(min > temp)
				{
					min  = temp;
				}
			}
		}
		return min;
	}
	public static void main(String[] argv)
	{
		Test t = new Test();
	}
}

- Ragnarok February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Main {
public static char get(char a, char b) {
if (a == 'a') {
if (b == 'b') return 'c';
else return 'b';
} else if (a == 'b') {
if (b == 'a') return 'c';
else return 'a';
} else {
if (b == 'b') return 'a';
else return 'b';
}
}
public static void main(String[] args) {
String test = "abbbbbbbbc";
for (int times = 0; times < test.length(); times++) {
StringBuffer sb = new StringBuffer();
sb.append(test.charAt(0));
for (int i = 1; i < test.length(); i++) {
if (test.charAt(i) != sb.charAt(sb.length() - 1)) {
char rep = get(test.charAt(i), sb.charAt(sb.length() - 1));
sb.deleteCharAt(sb.length() - 1);
sb.append(rep);
} else {
sb.append(test.charAt(i));
}
}
test = sb.toString();
}
System.out.println(test);
}
}

- Curt February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

is it working for "acbb". Optimally reduced string size should be 1

- Kaush February 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

does this work for "abcc". Optimally answer should be "c"

- Kaush February 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry for replying twice

- kaush702 February 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

take the array with O(n)

Walk through original array and whenever two adjacent character diff replace it and keep the final result in second array

apply the same with second array,

Repeat above procedure unless all elements are same or length equal to 1.

Time O(n^2)
Space O(n)

Space complexity can avoided if be put the result back to original array .

- Anonymous February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We should look for optimum solutions here. It is not enough if we just parse the elements from left to right or right to left. we must find out proper combinations to achieve maximum compression.
EG : cabb
Parsing from left to right yields -> cabb -> bbb -> String of lenght 3
Parsing from right to left yields -> cabb -> ccb -> ca-> b -> string of length 1.

Hence we must check when we combine two adjacent chars to produce the resultant char, if the resultant char is same as the next char. If so, skip this pair for that round and continue.

- Vijay Rajanna February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

in ur case CCAB will not work , i guess we need to store the min result and use dp to calculate for the next iteration

- Anonymous February 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

here is the idea:
(1) allocate an array of vector<string> size equal of length of the input array.
(2) initialize this array by pushing sub-string(inputstring, 0 , i)
(3) for each item from the array, domerge from the last char to the first char(merge reversely)and push newly generated string to the vector. try combining the tail char with all strings in its previous array element (i-1)
(4) loop (3) for all array elements
(5) the length of the shortest string in the last array element will be the answer.

- ben.wxc February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

here is the idea:
(1) allocate an array of vector<string> size equal of length of the input array.
(2) initialize this array by pushing sub-string(inputstring, 0 , i)
(3) for each item from the array, domerge from the last char to the first char(merge reversely)and push newly generated string to the vector. try combining the tail char with all strings in its previous array element (i-1)
(4) loop (3) for all array elements
(5) the length of the shortest string in the last array element will be the answer.

- ben.wxc February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

here is the idea:
(1) allocate an array of vector<string> size equal of length of the input array.
(2) initialize this array by pushing sub-string(inputstring, 0 , i)
(3) for each item from the array, domerge from the last char to the first char(merge reversely)and push newly generated string to the vector. try combining the tail char with all strings in its previous array element (i-1)
(4) loop (3) for all array elements
(5) the length of the shortest string in the last array element will be the answer.

- ben.wxc February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I also have an solution but in a recursive manner :

public class StringReduction {

	public char getChar(char l, char r) {

		if (l == 'a') {
			if (r == 'b')
				return 'c';
			if (r == 'c')
				return 'b';
		}
		if (l == 'b') {
			if (r == 'a')
				return 'c';
			if (r == 'c')
				return 'a';
		}
		if (l == 'c') {
			if (r == 'a')
				return 'b';
			if (r == 'b')
				return 'a';
		}
		return 'l';
	}

	public int redux(String input, int pos) {
		if (pos > input.length() - 1) {
			return input.length();
		}
		char l = input.charAt(pos);
		char r = input.charAt(pos + 1);
		if (l != r) {
			StringBuffer sb = new StringBuffer(getChar(l, r));
			sb.append(input.substring(pos + 1));
			System.out.println(sb.toString());
			return redux(sb.toString(), pos + 1);
		}
		return redux(input, pos + 1);
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		StringReduction sr = new StringReduction();
		System.out.println(sr.redux("aacbca", 0));

	}

}

- Dimitri February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Your solution seems to be a greedy method,
so it would not work for inputs like "abcc" which should be 1 in the optimal case.
ie.
"abcc" > "aac" > "ab" > "c" = 1

- Garukun August 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

find out the number of each characters NumA, NumB, NumB

If two of them 0 then return string.length
else if (all of them are either Odd or Even) return 2;

else return 1;

- Anonymous February 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can be solved using a stack..much the same way you would evaluate an expression(for eg infix)

- rakesh February 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <string.h>

#define A 'a'
#define B 'b'
#define C 'c'

void compress(char c[], int l) {

	int i=0;
	int sum=0, rem=0, avg;

	for (i=0;i<l;i++) sum += c[i];
	rem = sum % l;
	avg = sum / l;

	//check if all elements are same
	if((avg==A && !rem) || (avg==B && !rem) || (avg==C && !rem)) return;

	if(l==2) {
		c[0]=A+B+C-c[0]-c[1];
		c[1]='\0';
		return;
	}else{
		while((i+2)<l) {

			if((c[i+0]+c[i+1]+c[i+2])==(A+B+C)) {
				if(c[i+3]!=c[i+2])
					c[i+0]=c[i+2];
				else
					c[i+0]=c[i+1];
				
				memmove(&c[i+1], &c[i+2], l-i);
				c[l]='\0'; --l;
				continue;
			}
			i++;
		}


		i=0;
		while((i+1)<l)  {
			if(((c[i+0]+c[i+1])==(A+B))|| ((c[i+0]+c[i+1])==(B+C)) || ((c[i+0]+c[i+1])==(A+C))){
				c[i+0]=A+B+C-c[i+0]-c[i+1];
				memmove(&c[i+1], &c[i+2], l-i);
				c[l]='\0'; --l;
				continue;
			}
			i++;
			if(i==l && l>2)
				i=0;
		}

		compress(c,l);
	}
}

int main(void) {
	int i, len;
	char c[40];
	printf("Enter string {a,b,c}* : ");
	scanf("%s",c);
	len=strlen(c);
	printf("String is : %s\n",c);

	compress(c,len);
	printf("String is : %s\n",c);
	return 0;
}

- puri February 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <string.h>

#define A 'a'
#define B 'b'
#define C 'c'

void compress(char c[], int l) {

int i=0;
int sum=0, rem=0, avg;

for (i=0;i<l;i++) sum += c[i];
rem = sum % l;
avg = sum / l;

//check if all elements are same
if((avg==A && !rem) || (avg==B && !rem) || (avg==C && !rem)) return;

if(l==2) {
c[0]=A+B+C-c[0]-c[1];
c[1]='\0';
return;
}else{
while((i+2)<l) {

if((c[i+0]+c[i+1]+c[i+2])==(A+B+C)) {
if(c[i+3]!=c[i+2])
c[i+0]=c[i+2];
else
c[i+0]=c[i+1];

memmove(&c[i+1], &c[i+2], l-i);
c[l]='\0'; --l;
continue;
}
i++;
}


i=0;
while((i+1)<l) {
if(((c[i+0]+c[i+1])==(A+B))|| ((c[i+0]+c[i+1])==(B+C)) || ((c[i+0]+c[i+1])==(A+C))){
c[i+0]=A+B+C-c[i+0]-c[i+1];
memmove(&c[i+1], &c[i+2], l-i);
c[l]='\0'; --l;
continue;
}
i++;
if(i==l && l>2)
i=0;
}

compress(c,l);
}
}

int main(void) {
int i, len;
char c[40];
printf("Enter string {a,b,c}* : ");
scanf("%s",c);
len=strlen(c);
printf("String is : %s\n",c);

compress(c,len);
printf("String is : %s\n",c);
return 0;
}

- puri February 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Code for String manipulation:

correct me if i went wrong.........


#include<stdio.h>
#include<string.h>
void main()
{
int i;
char s[10]={'a','b','c','c','c','c','c','c','c'};
printf("\n\t");




for(i=0;i<10;i++)
{

if(s[1]=='b'&&s[2]=='c')
{
printf("aacccccc");
}

if(s[1]=='a'&&s[2]=='c')
{
printf("abccccc");
}

if(s[1]=='b'&&s[2]=='c')
{
printf("aacccc");
}


if(s[1]=='a'&&s[2]=='c')
{
printf("abccc");
}

if(s[1]=='b'&&s[2]=='c')
{
printf("aacc");
}

if(s[1]=='a'&&s[2]=='c')
{
printf("abc");
}

if(s[1]=='b'&&s[2]=='c')
{
printf("aa");

getch();
}

}
}












}}}

- subbu August 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Check my solution here:

basicalgos.blogspot.com/2012/02/string-reduction-given-string.html

- Andy February 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<map>
using namespace std;

string s;
map<string,int>mp;
map<string,string>change;
int get(string s)
{
int i,j;
int len=s.size();
int ans=len;
if(mp.count(s)!=0)
return mp[s];
for(i=0; i<s.size()-1; i++)
{
string now=s.substr(i,2);
if(change.count(now)!=0)
{
string tp=s.substr(0,i);
string tp1=s.substr(i+2,len-(i+2));
string tp2=change[now];
string next=tp1+tp+tp2;
ans=min(ans,get(next));
}
}
return mp[s]=ans;
}
int main()
{
int i,j,k,t;
freopen("in.txt","r",stdin);
scanf("%d",&t);
for(i=0; i<t; i++)
{
mp.clear();
change["ab"]="c";
change["ba"]="c";
change["ac"]="b";
change["ca"]="b";
change["cb"]="a";
change["bc"]="a";

cin>>s;
int ans;
ans=get(s);
cout<<ans<<endl;
}
}

- mabodx March 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<map>
using namespace std;

string s;
map<string,int>mp;
map<string,string>change;
int get(string s)
{
int i,j;
int len=s.size();
int ans=len;
if(mp.count(s)!=0)
return mp[s];
for(i=0; i<s.size()-1; i++)
{
string now=s.substr(i,2);
if(change.count(now)!=0)
{
string tp=s.substr(0,i);
string tp1=s.substr(i+2,len-(i+2));
string tp2=change[now];
string next=tp1+tp+tp2;
ans=min(ans,get(next));
}
}
return mp[s]=ans;
}
int main()
{
int i,j,k,t;
freopen("in.txt","r",stdin);
scanf("%d",&t);
for(i=0; i<t; i++)
{
mp.clear();
change["ab"]="c";
change["ba"]="c";
change["ac"]="b";
change["ca"]="b";
change["cb"]="a";
change["bc"]="a";

cin>>s;
int ans;
ans=get(s);
cout<<ans<<endl;
}
}

- mabodx March 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<map>
using namespace std;

string s;
map<string,int>mp;
map<string,string>change;
int get(string s)
{
int i,j;
int len=s.size();
int ans=len;
if(mp.count(s)!=0)
return mp[s];
for(i=0; i<s.size()-1; i++)
{
string now=s.substr(i,2);
if(change.count(now)!=0)
{
string tp=s.substr(0,i);
string tp1=s.substr(i+2,len-(i+2));
string tp2=change[now];
string next=tp1+tp+tp2;
ans=min(ans,get(next));
}
}
return mp[s]=ans;
}
int main()
{
int i,j,k,t;
freopen("in.txt","r",stdin);
scanf("%d",&t);
for(i=0; i<t; i++)
{
mp.clear();
change["ab"]="c";
change["ba"]="c";
change["ac"]="b";
change["ca"]="b";
change["cb"]="a";
change["bc"]="a";

cin>>s;
int ans;
ans=get(s);
cout<<ans<<endl;
}
}

- mabodx March 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<map>
using namespace std;

string s;
map<string,int>mp;
map<string,string>change;
int get(string s)
{
int i,j;
int len=s.size();
int ans=len;
if(mp.count(s)!=0)
return mp[s];
for(i=0; i<s.size()-1; i++)
{
string now=s.substr(i,2);
if(change.count(now)!=0)
{
string tp=s.substr(0,i);
string tp1=s.substr(i+2,len-(i+2));
string tp2=change[now];
string next=tp1+tp+tp2;
ans=min(ans,get(next));
}
}
return mp[s]=ans;
}
int main()
{
int i,j,k,t;
freopen("in.txt","r",stdin);
scanf("%d",&t);
for(i=0; i<t; i++)
{
mp.clear();
change["ab"]="c";
change["ba"]="c";
change["ac"]="b";
change["ca"]="b";
change["cb"]="a";
change["bc"]="a";

cin>>s;
int ans;
ans=get(s);
cout<<ans<<endl;
}
}

- mabodx March 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<map>
using namespace std;

string s;
map<string,int>mp;
map<string,string>change;
int get(string s)
{
int i,j;
int len=s.size();
int ans=len;
if(mp.count(s)!=0)
return mp[s];
for(i=0; i<s.size()-1; i++)
{
string now=s.substr(i,2);
if(change.count(now)!=0)
{
string tp=s.substr(0,i);
string tp1=s.substr(i+2,len-(i+2));
string tp2=change[now];
string next=tp1+tp+tp2;
ans=min(ans,get(next));
}
}
return mp[s]=ans;
}
int main()
{
int i,j,k,t;
freopen("in.txt","r",stdin);
scanf("%d",&t);
for(i=0; i<t; i++)
{
mp.clear();
change["ab"]="c";
change["ba"]="c";
change["ac"]="b";
change["ca"]="b";
change["cb"]="a";
change["bc"]="a";

cin>>s;
int ans;
ans=get(s);
cout<<ans<<endl;
}
}

- mabodx March 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<map>
using namespace std;

string s;
map<string,int>mp;
map<string,string>change;
int get(string s)
{
int i,j;
int len=s.size();
int ans=len;
if(mp.count(s)!=0)
return mp[s];
for(i=0; i<s.size()-1; i++)
{
string now=s.substr(i,2);
if(change.count(now)!=0)
{
string tp=s.substr(0,i);
string tp1=s.substr(i+2,len-(i+2));
string tp2=change[now];
string next=tp1+tp+tp2;
ans=min(ans,get(next));
}
}
return mp[s]=ans;
}
int main()
{
int i,j,k,t;
freopen("in.txt","r",stdin);
scanf("%d",&t);
for(i=0; i<t; i++)
{
mp.clear();
change["ab"]="c";
change["ba"]="c";
change["ac"]="b";
change["ca"]="b";
change["cb"]="a";
change["bc"]="a";

cin>>s;
int ans;
ans=get(s);
cout<<ans<<endl;
}
}

- mabodx March 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<map>
using namespace std;

string s;
map<string,int>mp;
map<string,string>change;
int get(string s)
{
int i,j;
int len=s.size();
int ans=len;
if(mp.count(s)!=0)
return mp[s];
for(i=0; i<s.size()-1; i++)
{
string now=s.substr(i,2);
if(change.count(now)!=0)
{
string tp=s.substr(0,i);
string tp1=s.substr(i+2,len-(i+2));
string tp2=change[now];
string next=tp1+tp+tp2;
ans=min(ans,get(next));
}
}
return mp[s]=ans;
}
int main()
{
int i,j,k,t;
freopen("in.txt","r",stdin);
scanf("%d",&t);
for(i=0; i<t; i++)
{
mp.clear();
change["ab"]="c";
change["ba"]="c";
change["ac"]="b";
change["ca"]="b";
change["cb"]="a";
change["bc"]="a";

cin>>s;
int ans;
ans=get(s);
cout<<ans<<endl;
}
}

- mabodx March 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<map>
using namespace std;

string s;
map<string,int>mp;
map<string,string>change;
int get(string s)
{
int i,j;
int len=s.size();
int ans=len;
if(mp.count(s)!=0)
return mp[s];
for(i=0; i<s.size()-1; i++)
{
string now=s.substr(i,2);
if(change.count(now)!=0)
{
string tp=s.substr(0,i);
string tp1=s.substr(i+2,len-(i+2));
string tp2=change[now];
string next=tp1+tp+tp2;
ans=min(ans,get(next));
}
}
return mp[s]=ans;
}
int main()
{
int i,j,k,t;
freopen("in.txt","r",stdin);
scanf("%d",&t);
for(i=0; i<t; i++)
{
mp.clear();
change["ab"]="c";
change["ba"]="c";
change["ac"]="b";
change["ca"]="b";
change["cb"]="a";
change["bc"]="a";

cin>>s;
int ans;
ans=get(s);
cout<<ans<<endl;
}
}

- mabodx March 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<map>
using namespace std;

string s;
map<string,int>mp;
map<string,string>change;
int get(string s)
{
int i,j;
int len=s.size();
int ans=len;
if(mp.count(s)!=0)
return mp[s];
for(i=0; i<s.size()-1; i++)
{
string now=s.substr(i,2);
if(change.count(now)!=0)
{
string tp=s.substr(0,i);
string tp1=s.substr(i+2,len-(i+2));
string tp2=change[now];
string next=tp1+tp+tp2;
ans=min(ans,get(next));
}
}
return mp[s]=ans;
}
int main()
{
int i,j,k,t;
freopen("in.txt","r",stdin);
scanf("%d",&t);
for(i=0; i<t; i++)
{
mp.clear();
change["ab"]="c";
change["ba"]="c";
change["ac"]="b";
change["ca"]="b";
change["cb"]="a";
change["bc"]="a";

cin>>s;
int ans;
ans=get(s);
cout<<ans<<endl;
}
}

- mabodx March 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

string reduce (string toReduce)
{
    string [] paths = new srtring [6];
    string min = toReduce;

    path[0] = toReduce.replace('ac', 'b');
    path[1] = toReduce.replace('ab', 'c');
    path[2] = toReduce.replace('bc', 'a');
    path[3] = toReduce.replace('cb', 'a');
    path[4] = toReduce.replace('ca', 'b');
    path[5] = toReduce.replace('ba', 'c');

    for (int i = 0; i < 6; i++)
    {
        if (path[i] != toReduce) 
            path [i] = reduce (path[i]);
        if (path[i].length < min.length) min = path[i];
    }
    return min;
}

- .w.h.i.m. March 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solvable with no code. If all three types have either an even or odd number, then the smallest string has size 2. Otherwise 1. Or a special case like he original string is all 1 char which can be treated separately.

To see this consider that e odd/even imbalance is preserved by any combination. If all are even or odd, then a combination switches their mode from all even to all odd or vice versa since the two combined lose 1 and the created char gains one. Similarly an imbalance keeps the imbalance but switches it from odd to even or vice versa.

Thus no combination can ever get you from all odd or even to 1 char left since zero is not odd. This does not fully prove our assertion since it does not prove that all cases are reducible to 2 or 1. That is easily shown by proving that any imbalance is easily reduced to an off by one case e.g. 4/4/5. I leave that up to readers.

- Anonymous April 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

char replace(char char1, char char2)
{
if((char1=='a' && char2=='b') || (char1=='b' && char2=='a')) return 'c';
else if((char1=='a' && char2=='c') || (char1=='c' && char2=='a')) return 'b';
else return 'a';
}
int main()
{
string a = "bcabccc";
for(int i=0 ;i+1<a.length(); i++)
{
if(a[i]!=a[i+1])
{
a[i] = replace(a[i],a[i+1]);
a.erase(i+1,1);
i= (i-2<-1)?-1:i-2;
}
cout << a <<" ";
}

cout <<a.length();

- ediston April 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Count the number of occurences of each letter in the input string [numA, numB, numC]

If two of these counts are 0, then return string.length

Else if (all counts are even) or (all counts are odd), then return 2

Else, then return 1

- sunny April 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int MinOfChars(int *Arr,int PrevSum)
{
	if(Arr[0] != 0 && (Arr[1] == 0 && Arr[2] == 0))
		return (Arr[0]);
	if(Arr[1] != 0 && (Arr[0] == 0 && Arr[2] == 0))
		return (Arr[1]);
	if(Arr[2] != 0 && (Arr[0] == 0 && Arr[1] == 0))
		return (Arr[2]);

	int CurrSum = Arr[0] + Arr[1] + Arr[2];

	if(PrevSum == CurrSum)
		return CurrSum;

	sort(Arr,Arr + 3);

	Arr[2] -= Arr[1];
	Arr[0] += Arr[1];
	Arr[1] = 0;

	return(MinOfChars(Arr,CurrSum));
}

int MinOfChars(char *S)
{
	int Arr[3] = {0,0,0};
	
	for(int i = 0; i < strlen(S); ++i)
	{
		Arr[S[i] - 'a']++;
	}

	return MinOfChars(Arr,-1);
}

- Anonymous May 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int MinOfChars(int *Arr,int PrevSum)
{
	if(Arr[0] != 0 && (Arr[1] == 0 && Arr[2] == 0))
		return (Arr[0]);
	if(Arr[1] != 0 && (Arr[0] == 0 && Arr[2] == 0))
		return (Arr[1]);
	if(Arr[2] != 0 && (Arr[0] == 0 && Arr[1] == 0))
		return (Arr[2]);

	int CurrSum = Arr[0] + Arr[1] + Arr[2];

	if(PrevSum == CurrSum)
		return CurrSum;

	sort(Arr,Arr + 3);

	Arr[2] -= Arr[1];
	Arr[0] += Arr[1];
	Arr[1] = 0;

	return(MinOfChars(Arr,CurrSum));
}

int MinOfChars(char *S)
{
	int Arr[3] = {0,0,0};
	
	for(int i = 0; i < strlen(S); ++i)
	{
		Arr[S[i] - 'a']++;
	}

	return MinOfChars(Arr,-1);
}

- Anonymous May 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class StringReduction {

	StringReduction() {
	}

	private int allEqual(String str) {
		boolean ret = true;

		char pc;

		if (str.length() == 1)
			return 1;

		char[] ca = str.toCharArray();

		pc = ca[0];

		for (int i = 1; i < ca.length; i++) {
			if (ca[i] != pc)
				return 0;
			pc = ca[i];
		}

		return ca.length;
	}

	private String replaceTwo(String str, int i) {
		if (str == null)
			throw new NullPointerException();

		if (str.length() == 1)
			return str;

		if (str.length() - 1 < i + 1)
			return str;// do not replace

		char[] ca = str.toCharArray();
		char replaceC = '\0';

		if (ca[i] == ca[i + 1])
			return str;

		if (ca[i] == 'a' && ca[i + 1] == 'b') {
			replaceC = 'c';
		} else if (ca[i] == 'b' && ca[i + 1] == 'c') {
			replaceC = 'a';
		} else if (ca[i] == 'c' && ca[i + 1] == 'a') {
			replaceC = 'b';
		}

		if (i > 0 && (i + 2) < str.length()) {
			return (i > 1) ? str.substring(0, i - 1) + replaceC
					+ str.substring(i + 2) : ca[0] + replaceC
					+ str.substring(i + 2);
		} else if (i == 0 && (i + 2) < str.length()) {
			return replaceC + str.substring(i + 2);
		} else if (i > 0 && (i + 2) >= str.length()) {
			return (i > 1) ? str.substring(0, i - 1) + replaceC : "" + ca[0] + replaceC;
		} else if (i == 0 && (i + 2) >= str.length()) {
			return replaceC + "";
		}

		return "";
	}

	private int min(int a, int b) {
		if (a > b)
			return b;
		else
			return a;
	}

	public int stringReduced(String str, int i) {
		if (str.length() == 1)
			return 1;

		if (this.allEqual(str) > 0 || str.length() == i)
			return str.length();

		String reduceString = this.replaceTwo(str, i);

		int reduceVal = 0;

		if (reduceString.equals(str)) {
			reduceVal = stringReduced(str, i + 1);
		} else {
			reduceVal = stringReduced(reduceString, 0);
		}

		int noreduceVal = stringReduced(str, i + 1);

		return min(noreduceVal, reduceVal);
	}
}

- mm May 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution{

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine().toString());
		for (int i = T; --i >= 0;) {
			String S = br.readLine();
			if (S.length() < 2) {
				System.out.println(S.length());
			} else {
				process(S);
			}
		}
		
	}

	private static void process(String S) {
		for (int i = 0; i < S.length() - 1; i++) {
			String temp = S.substring(i, i + 2);
			if (temp.contains("ab") || temp.contains("ba")) {
				S = S.replaceFirst(temp, "c");
				i = -1;
			} else if (temp.contains("ac") || temp.contains("ca")) {
				S = S.replaceFirst(temp, "b");
				i = -1;
			} else if (temp.contains("bc") || temp.contains("cb")) {
				S = S.replaceFirst(temp, "a");
				i = -1;
			}
		}
		System.out.println(S.length());

	}
}

- Naveen July 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#import<stdio.h>
#import<string.h>
char diff(char a, char b)
{
	if((a == 'a' && b == 'b') || (a == 'b' && b == 'a'))
		return 'c';
	else if((a == 'b' && b == 'c') || (a == 'c' && b == 'b'))
		return 'a';
	else if((a == 'a' && b == 'c') || (a == 'c' && b == 'a'))
		return 'b';
	else
		return '@';
}
void  moveZeros(char* a)
{
        size_t len = strlen(a);
        int index0 = 0;
        int indexN = 0;
	printf("-->before %s",a);
        for(int i = 0; i < len; i++)
        {
                if(a[i] != '@')
                {
                        int temp = a[i];
                        a[i] = a[index0];
                        a[index0] = temp;
                        index0++;
                }
        }
	a[index0] = '\0';
	printf("--> %s",a);
}

void stringCompression(char* str, size_t len)
{
	int i = 0;
	int j;
	int cont = 1;
	while(cont == 1){
		i = 0;
		cont = 0;
		for(j = 1; j < len;)
		{
			char r = diff(str[i], str[j]);
			if(r != '@')
			{
				cont = 1;
				str[i] = r;
				str[j] = '@';
				i++; 
			}
			else
				i = j;
			j++;	
		}
		moveZeros(str);
	}
	printf("\t%lu\n",strlen(str));
}

int main()
{
	char a[] = "acbb";
	char b[] = "aaaabbbb";
	char c[] = "aaa";
	char d[] = "acacac";

	printf("For %s :",a);
	stringCompression(a, strlen(a));
	printf("For %s :",b);
	stringCompression(b, strlen(b));
	printf("For %s :",c);
	stringCompression(c, strlen(c));
	printf("For %s :",d);
	stringCompression(d, strlen(d));
}

This code scans the array from left to right, and replaces them.

- Anonymous July 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

IN JAVA:

public class StringReduction{
static HashMap<String, String> map = new HashMap<String, String>();
static List<Integer> len = new ArrayList<Integer>();
static{
map.put("ab", "c");
map.put("ba", "c");
map.put("ac", "b");
map.put("ca", "b");
map.put("bc", "a");
map.put("cb", "a");

}
public static void main(String args[]) throws Exception {

reduce("abaaccbca");
Collections.sort(len);
System.out.println(len.get(0));
}
static void reduce(String s){
Object combinations[] = getCombinations(s);
//int count = 0;
for(Object comb : combinations){
if(map.containsKey((String)comb)){

reduce(s.replace((String)comb, map.get((String)comb)));
}
}
len.add(s.length());
}

static Object[] getCombinations(String s){
ArrayList<String> list = new ArrayList<String>();
for(int i = 0;i<s.length()-1; i++){
list.add(s.charAt(i)+""+s.charAt(i+1));
}
return list.toArray();
}
}
}

- BS August 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is easily solvable in time O(n). Just observe that the reduction rules are the same as multiplication in Klein 4 group.

- Koala January 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def reduce_chars(chars):
        yield chars
        for i, c in enumerate(chars[:-1]):
            if c != chars[i + 1]:
                sub = 'abc'.translate(None, chars[i:i + 2])
                for rc in reduce_chars(chars[:i] + sub + chars[i + 2:]):
                    yield rc

def get_min_reduction(chars):
    return min([len(c) for c in reduce_chars(chars)])

- Anonymous April 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void smalleststring(String s) {

        int res = s.length();
        Queue<String> queue = new LinkedList<String>();
        queue.add(s);

        while(! queue.isEmpty()) {
            s = queue.poll();
            char[] ch = s.toCharArray();
            if(ch.length == 1 ||  same(ch)) {
                res = Math.min(res, ch.length);
                continue;
            }

            for(int i=0; i<ch.length - 1; i++) {

                if(ch[i] != ch[i+1]) {
                    StringBuilder sb = new StringBuilder();
                    sb.append(s);
                    char c =  (char) ('a' + (3- (ch[i] + ch[i+1] - 'a' -'a')));
                    sb.replace(i, i+2, String.valueOf(c));
                    if (! queue.contains(sb.toString())) {
                        queue.add(sb.toString());
                    }
                }
            }


        }

         System.out.println("res: "+ res);
    }

    public boolean same(char[] ch) {
        for(int i= 0 ; i <ch.length - 1; i++) {
            if(ch[i] != ch[i+1]) {
                      return false;
            }
        }
        return true;
    }

- radhakrishna October 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

192 1. put chars in a link list ( can use doubly link list)
  193 2. p1 = start of list
  194 3. p2 = p1->next;
  195 4. while (all elements in list become same) {
  196 
  197         while(p2!=NUL){
  198                 if(p1=>value != p2->value){
  199                 p2 = p2->next;
  200                 p2->value = replace with 3rd char
  201                 del(p2);
  202 
  203                 } else {
  204                 p2 = p2->next;
  205                 p1 = p1->next;
  206                 }
  207         }
  208 }
  209 
  210 5. after the loop ends all chars will be same. get the lenth of link list
  211 6. Reverse the orginal link list
  212 8. run step 4 on reversed link list 
  213 9. get the length on the list obtained in step 8
  214 10 return the min len of step 5 and 9

- vivekh August 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<string.h>
#include<stdbool.h>
#define MAXN 105

char str[MAXN];
int dp[3][MAXN], canDP[MAXN][MAXN][3], vis[MAXN][MAXN][3], cs;
const int INF = 1000000;

inline int min(int u, int v) {return u < v ? u : v;}

bool Can(int st, int ed, char ch)
{
//Can we reduce the substring [st, ed] to a single character ch?

if(st == ed) return (str[st] == ch);
if(vis[st][ed][ch] == cs) return canDP[st][ed][ch];
vis[st][ed][ch] = cs;

int u, v, k;
if(ch == 0) u = 1, v = 2;
if(ch == 1) u = 0, v = 2;
if(ch == 2) u = 0, v = 1;

for(k = st; k < ed; k++)
if( (Can(st, k, u) && Can(k+1, ed, v)) || (Can(st, k, v) && Can(k+1, ed, u)) )
return canDP[st][ed][ch] = true;

return canDP[st][ed][ch] = false;
}

int main()
{
int i, j, tcase;
int len, ch;

scanf("%d", &tcase);
while(tcase--)
{
cs++;
scanf("%s", str + 1);
len = strlen( str + 1);

for(i = 1; i <= len; i++) str[i] -= 'a'; // Replacing a, b & c with 0, 1 & 2.
for(ch = 0; ch < 3; ch++)
for(i = 1; i <= len; i++)
{
dp[ch][i] = INF;
for(j = 1; j <= i; j++)
if( Can(j, i, ch) )
dp[ch][i] = min(dp[ch][i], dp[ch][j-1] + 1);
}

printf("%d\n", min(dp[0][len], min(dp[1][len], dp[2][len])));
}
return 0;
}

- Kumaar September 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<string.h>
#include<stdbool.h>
#define MAXN 105

char str[MAXN];
int dp[3][MAXN], canDP[MAXN][MAXN][3], vis[MAXN][MAXN][3], cs;
const int INF = 1000000;

inline int min(int u, int v) {return u < v ? u : v;}

bool Can(int st, int ed, char ch)
{
//Can we reduce the substring [st, ed] to a single character ch?

if(st == ed) return (str[st] == ch);
if(vis[st][ed][ch] == cs) return canDP[st][ed][ch];
vis[st][ed][ch] = cs;

int u, v, k;
if(ch == 0) u = 1, v = 2;
if(ch == 1) u = 0, v = 2;
if(ch == 2) u = 0, v = 1;

for(k = st; k < ed; k++)
if( (Can(st, k, u) && Can(k+1, ed, v)) || (Can(st, k, v) && Can(k+1, ed, u)) )
return canDP[st][ed][ch] = true;

return canDP[st][ed][ch] = false;
}

int main()
{
int i, j, tcase;
int len, ch;

scanf("%d", &tcase);
while(tcase--)
{
cs++;
scanf("%s", str + 1);
len = strlen( str + 1);

for(i = 1; i <= len; i++) str[i] -= 'a'; // Replacing a, b & c with 0, 1 & 2.
for(ch = 0; ch < 3; ch++)
for(i = 1; i <= len; i++)
{
dp[ch][i] = INF;
for(j = 1; j <= i; j++)
if( Can(j, i, ch) )
dp[ch][i] = min(dp[ch][i], dp[ch][j-1] + 1);
}

printf("%d\n", min(dp[0][len], min(dp[1][len], dp[2][len])));
}
return 0;
}

- Kumaar September 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include "algorithm"
#include "iostream"
#include "numeric"
#include "iomanip"
#include "cstring"
#include "math.h"
#include "bitset"
#include "string"
#include "vector"
#include "ctime"
#include "queue"
#include "stack"
#include "map"
#include "set"

#include "ext/pb_ds/assoc_container.hpp" // Common file
#include "ext/pb_ds/tree_policy.hpp" // Including tree_order_statistics_node_update
#include "ext/pb_ds/detail/standard_policies.hpp"

using namespace std;
using namespace __gnu_pbds;


#define f first
#define lgn 25
#define endl '\n'
#define sc second
#define pb push_back
#define N (int) 200+5
#define PI acos(-1.0)
#define int long long
#define vi vector<int>
#define mod 1000000007
#define ld long double
#define eb emplace_back
#define mii map<int,int>
#define vpii vector<pii>
#define pii pair<int,int>
#define pq priority_queue
#define BLOCK (int)sqrt(N)
#define test(x) while(x--)
#define all(x) begin(x),end(x)
#define allr(x) x.rbegin(),x.rend()
#define fo(i,a,n) for(int i=a;i<n;i++)
#define rfo(i,n,a) for(int i=n;i>=a;i--)
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define time() cerr << "Time : " << (double)clock() / (double)CLOCKS_PER_SEC << "s\n"
#define bug(...) __f (#__VA_ARGS__, __VA_ARGS__)

typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update >
OS ;

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
const char* comma = strchr (names + 1, ',');
cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

const int inf = 0x3f3f3f3f;
const int INF = 0x3f3f3f3f3f3f3f3f;

int n,m,k,q;
string s;
int dp[N][N]; // dp[i][j] -> minimum length we can formed in interval (i,j)
int val[N][N]; // val[i][j] -> updated value for any interval
// let a -> 1 , b -> 2 and c -> 3

void go()
{
cin >> s;
n = s.size();
s = " " + s;

memset( dp , 0, sizeof dp );
memset( val , 0 , sizeof val );

for( int i = 1; i <= n; i++)
{
for( int j = i; j <= n; j++)
{
if( i == j )
{
if( s[i] == 'a' ) val[i][i] = 1;
if( s[i] == 'b' ) val[i][i] = 2;
if( s[i] == 'c' ) val[i][i] = 3;
}

dp[i][j] = ( j - i + 1); // mark the length
}
}

for(int gap = 1; gap <= n; gap++)
{
for( int i = 1; i + gap <= n; i++)
{
int j = i + gap;

for( int k = i; k < j; k++)
{
dp[i][j] = min( dp[i][j] , dp[i][k] + dp[k+1][j] );

int sum = val[i][k] + val[k+1][j];

if( val[i][k] and val[k+1][j] and val[i][k] != val[k+1][j] and dp[i][j] > 0)
{
if( sum == 3 ) val[i][j] = 3;
if( sum == 4 ) val[i][j] = 2;
if( sum == 5 ) val[i][j] = 1;

dp[i][j] = min( dp[i][j] , max(1LL , dp[i][j] - 1) );
}
}
}
}

cout << dp[1][n] << endl;

}

int32_t main()
{
FAST;
int t=1;
cin>>t;
test(t) go();
}

- Use DP on interval May 06, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

The smallest we can get is the length of smallest substring formed by similar consecutive elements.
e.g. abcbac ( smallest consecutive is 1 ) so string reduces to size 1.
conside aaaabbbccccc ( a4,b3,c5) it should reduce to 3 since smallest consecutive similar is 3 )

aaaabbbccccc -> aaaabbacccc ->
aaaabbacc -> aaaabccc -> aaacccc -> aabccc -> aaa. (length is 3)

- Mandar November 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

suppose aaa is the given string, if we apply the process repeatedly, it can get reduced to size 1.
aaa->aa->a
I dint get the question.

- Anonymous November 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The string should contain of atleast two of the three characters otherwise your solution won't work either. what if it's just aaa or bbbbbbbbb or cccccc or aaaaaaaaaaa :) still searchinf for a better counter example though. cheers!

- Algo Visa November 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

aaabbbb
smallest consecutive is 3 but reduces to 1

- anonymous November 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

aaacccc -> aabccc -> acccc -> bccc -> acc -> bc -> c. (length is 1)
So, length could be different if different reduction is processed.

- Anonymous November 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

take the array with O(n)

Walk through original array and whenever two adjacent character diff replace it and keep the final result in second array

apply the same with second array,

Repeat above procedure unless all elements are same or length equal to 1.

Time O(n^2)
Space O(n)

Space complexity can avoided if be put the result back to original array .

- Anonymous February 20, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More