Решение алгоритма сокращения строки

Я готовлюсь к интервью, которое у меня в понедельник, и я нашел эту проблему, чтобы решить, называемую " сокращение строки". Задача формулируется следующим образом:

Учитывая строку, состоящую из a, b и c, мы можем выполнить следующее
операция: Возьмите любые два соседних различных символа и замените их
с третьим персонажем. Например, если " А " и " с " соседние,
их можно заменить на "б". Что такое самая маленькая струна, которая может
результат применения эта операция повторялась неоднократно?

Например, cab - > cc или cab - > bb, что приводит к строке длины
2. Для этого одно оптимальное решение: bcab - > aab - > ac - > b. больше никакие операции не могут быть применены, и результирующая строка имеет длину 1.
Если строка = CCCCC, никакие операции не могут быть выполнены, и поэтому
ответ-5.

Я видел много вопросов и ответов на stackoverflow, но я хотел бы проверить свой собственный алгоритм. Вот мой алгоритм в псевдокод. В моем коде

1. S - это моя строка для сокращения


2. S[i] - символ в индексе i


3. P-это стек:


4. 
   

   Redux-это функция, которая уменьшает символы.

   
   
   

   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)}
   
   

   
   

Худший вариант моих алгоритмов-O (n), потому что все операции в стеке P выполняются на O(1). Я попробовал этот алгоритм в примерах выше, я получаю ожидаемые ответы.
Позвольте мне выполнить мое algo с этим примером " 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 

            car = reduction (car, popped) = reduction (a,c) = b

            P = {∅}

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



... and it continues until n

I запустили этот алгоритм на различных примерах, вроде этого, похоже, работает.
Я написал код на Java, который тестирует этот алгоритм, когда я отправляю свой код в систему, я получаю неправильные ответы. Я разместил код java на gisthub, чтобы вы могли его увидеть.