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

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

Имея строку, состоящую из 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 — функция, которая сокращает символы.

   функция редукции(S[1..n]){
   P = создать_пустой_стек();
   для i = от 1 до n
   делать
   автомобиль = S[i];
   пока (непусто(P))
   делать
   голова = заглянуть (р);
   если(голова == машина) сломать;
   еще {
   выскочил = поп (P);
   car = redux (автомобиль, выскочил);
    }
   Готово
   толкать (автомобиль)
   Готово
   возвращаемый размер(P)}
   

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

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

Кто-нибудь может сказать мне, что не так с моим алгоритмом.