Take the 2-minute tour ×

I am preparing myself for an interview that I have on monday and I found this problem to resolve called "String Reduction". The problem is stated like this :

Given a string consisting of a,b and c's, we can perform the following operation: Take any two adjacent distinct characters and replace it with the third character. For example, if 'a' and 'c' are adjacent, they can replaced with 'b'. What is the smallest string which can result by applying this operation repeatedly?

For instance, cab -> cc or cab -> bb, resulting in a string of length 2. For this one, one optimal solution is: bcab -> aab -> ac -> b. No more operations can be applied and the resultant string has length 1. If the string is = CCCCC, no operations can be performed and so the answer is 5.

I have seen a lot questions and answers on stackoverflow but I would like to verify my own algorithm. Here is my algorithm in pseudo code. In my code

  1. S is my string to reduce
  2. S[i] is the character at index i
  3. P is a stack:
  4. redux is the function that reduces the characters.

    function reduction(S[1..n]){        
    P = create_empty_stack();
    for i = 1 to n
       car = S[i];
       while (notEmpty(P))
          head = peek(p);
          if( head == car) break;
          else {
             popped = pop(P);
             car = redux (car, popped);
    return size(P)}

The worst-case of my algorithms is O(n) because all the operations on the stack P is on O(1). I tried this algorithm in the examples above, I get the expected answers. Let me execute my algo with this example " abacbcaa" :

i = 1 :
   car = S[i] = a, P = {∅}
   P is empty, P = P U {car} -> P = {a}

 i = 2 :
   car = S[i] = b, P = {a}
   P is not empty :
       head = a
       head != car ->
            popped = Pop(P) = a 
            car = reduction (car, popped) = reduction (a,b) = c
            P = {∅}

    push(car, P) -> P = {c}

i = 3 :
   car = S[i] = a, P = {c}
   P is not empty :
       head = c
       head != car ->
            popped = Pop(P) = c 
            car = reduction (car, popped) = reduction (a,c) = b
            P = {∅}

    push(car, P) -> P = {b}


 i = 5 : (interesting case)
  car = S[i] = c, P = {c}
   P is not empty :
       head = c
       head == car -> break

    push(car, P) -> P = {c, c}

 i = 6 :
  car = S[i] = b, P = {c, c}
   P is not empty :
       head = c
       head != car ->
            popped = Pop(P) = c 
            car = reduction (car, popped) = reduction (b,c) = a
            P = {c}

   P is not empty : // (note in this case car = a)
       head = c
       head != car ->
            popped = Pop(P) = c 
            P = {∅}

... and it continues until n

I have run this algorithm on various examples like this, it seems to work. I have written a code in Java that test this algorithm, when I submit my code to the system, I am getting wrong answers. I have posted the java code on gisthub so you can see it.

Can someone tell me what is wrong with my algorithm.

share|improve this question
It is asking for the smallest string, then it means if there are more than one way to reduce the string, you have to find it. You seem to only search for the first way of reduction, of course, it will fail. Sometimes, not using a rule and wait for more characters to come may result in a better result. –  nhahtdh May 26 '12 at 13:06
@acattle yeap, but only in the first case, the first character. In every for-loop, the stack will have at least one character. –  Dimitri May 26 '12 at 13:29
@nhahtdh can you be more specific?? –  Dimitri May 26 '12 at 13:38
I don't think it is possible to obtain a O(n) algorithm... –  UmNyobe May 26 '12 at 14:00
this simple algorithm might be useful jsfiddle.net/YFw4G JavaScript is easy to understand –  ajax333221 Jun 29 '12 at 19:03

2 Answers 2

up vote 5 down vote accepted

I am going to try to explain what nhahtdh means. There are multiple reasons why your algorithm fails. But the most fundamental one is that at each point in time, only the first character observed has a chance to be pushed on the stack p. It should not be this way, as you can start a reduction basically from any position.

Let me give you the string abcc. If I breakpoint at

car = S[i];

The algo run as :

p = {∅}, s = _abcc //underscore is the position
p = {a}, s = a_bcc  
p = {c}, s = ab_cc  

At this point you are stuck with a reduction ccc

But there is another reduction : abcc -> aac ->ab ->c

Besides, returning the size of the stack P is wrong. cc cannot be reduced, but the algorithm will return 1. You should also count the number of times you skip.

share|improve this answer
OK, you are totally right –  Dimitri May 26 '12 at 14:30
If I use a randomized index, do you think it will work? –  Dimitri May 26 '12 at 14:46
No. You need to cover ALL cases. Naively for a given string of size n there are n-1 redux leading to n-1 strings of size n-1. this lead to a n! complexity, which is catastrophic. There must be a way (dyn. programming, etc...) to reduce this complexity. –  UmNyobe May 26 '12 at 14:50

you can also solve this question using brute force...and recursion

for all n-1 pairs(2 char) replace it with 3rd char if possible and apply reduce on this new string of length n-1
    for all n-2 pairs replace it with 3rd char and apply reduce on new string
         for all n-3 pairs....and so on

The new string of length n-1 will have n-2 pairs and similarly new string of length n-2 will have n-3 pairs.

while applying this approach keep storing the minimum value

if (new_min < min)
    min = new_min

Implementation: http://justprogrammng.blogspot.com/2012/06/interviewstreet-challenge-string.html

share|improve this answer

Your Answer


