title: Solving String reduction Algorithm
body: <p>I am preparing myself for an interview that I have on monday and I found this problem to resolve called "<a href="https://www.interviewstreet.com/challenges/dashboard/#problem/4eac48496bee2" rel="nofollow noreferrer">String Reduction</a>". The problem is stated like this : </p>
  
  <blockquote>
    <p>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?</p>
    
    <p>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.</p>
  </blockquote>
  
  <p>I have seen a lot <a href="https://stackoverflow.com/questions/8551519/string-reduction-programming-contest-solution-needed">questions and answers</a> on stackoverflow but I would like to verify my own algorithm. Here is my algorithm in pseudo code. In my code</p>
  
  <ol>
  <li>S is my string to reduce</li>
  <li>S[i] is the character at index i</li>
  <li>P is a stack:</li>
  <li><p>redux is the function that reduces the characters.</p>
  
  <pre><code>function reduction(S[1..n]){        
  P = create_empty_stack();
  for i = 1 to n
  do
     car = S[i];
     while (notEmpty(P))
     do
        head = peek(p);
        if( head == car) break;
        else {
           popped = pop(P);
           car = redux (car, popped);
         }  
     done
     push(car)
  done
  return size(P)}
  </code></pre></li>
  </ol>
  
  <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 " <em>abacbcaa</em>" :</p>
  
  <pre><code>i = 1 :
     car = S[i] = a, P = {∅}
     P is empty, P = P U {car} -&gt; P = {a}
  
   i = 2 :
     car = S[i] = b, P = {a}
     P is not empty :
         head = a
         head != car -&gt;
              popped = Pop(P) = a 
              car = reduction (car, popped) = reduction (a,b) = c
              P = {∅}
  
      push(car, P) -&gt; P = {c}
  
  
  
  i = 3 :
     car = S[i] = a, P = {c}
     P is not empty :
         head = c
         head != car -&gt;
              popped = Pop(P) = c 
              car = reduction (car, popped) = reduction (a,c) = b
              P = {∅}
  
      push(car, P) -&gt; P = {b}
  
  
   ...
  
  
   i = 5 : (interesting case)
    car = S[i] = c, P = {c}
     P is not empty :
         head = c
         head == car -&gt; break
  
      push(car, P) -&gt; P = {c, c}
  
  
   i = 6 :
    car = S[i] = b, P = {c, c}
     P is not empty :
         head = c
         head != car -&gt;
              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 -&gt;
              popped = Pop(P) = c 
              car = reduction (car, popped) = reduction (a,c) = b
              P = {∅}
      push(car, P) -&gt; P = {b}
  
  ... and it continues until n
  </code></pre>
  
  <p>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 <a href="https://gist.github.com/2793850" rel="nofollow noreferrer">gisthub</a>  so you can see it. </p>
  
  <p>Can someone tell me what is wrong with my algorithm. </p>