Проверка, может ли строка «a» и «b» быть уменьшена до пустой, если дубликаты возникают последовательно ⇐ Python

[Anonymous]

Я пытаюсь решить эту проблему с помощью O(n), поэтому использую стек. В этом коде:

Код: Выделить всё

def can_reduce_to_empty(s):
stack = []  # Stack to store character groups [char, count]

for char in s:
# Check if the stack has a group and the top matches the current character
if stack and stack[-1][0] == char:
stack[-1][1] += 1  # Increment the count of the top group

# If the group has >= 2 characters, pop it
if stack[-1][1] >= 2:
stack.pop()

while len(stack) >= 2 and stack[-1][0] == stack[-2][0]:
stack[-2][1] += stack[-1][1]
stack.pop()
else:
# Start a new group with count 1
stack.append([char, 1])

# If the stack is empty, the string can be reduced to empty
return 1 if not stack else 0

s = "babbbaaabb"
print(can_reduce_to_empty(s))  # Output SHOULD BE: 1

Проблема в том, что я получаю на выходе 0, хотя должно быть 1
Я пробовал использовать матрицу что привело к той же проблеме, так что я предполагаю, что это логическая ошибка?
Контекст: нам дана строка s из двух символов 'a' и 'b'. Пусть группа — максимальная последовательная подстрока одного и того же символа. Любую группу g из s длиной не менее двух можно удалить (или вытолкнуть), а новую строку создать путем объединения оставшихся левой и правой подстрок s. Мы повторяем этот процесс до тех пор, пока строка не станет пустой строкой или не останется групп длиной не менее двух.
Например, строка s = babbbbaaabb имеет 5 групп b, a, bbb, aaa и bb. Строку s можно превратить в пустую строку, извлекая группы в следующей последовательности (подчеркнутая группа должна быть извлечена в последовательности):
babbbaaabb → baaaabb → bbb → пустая строка
Но группа может не обращаться к пустой строке с помощью другой последовательности операций pop:
babbbaaabb → babbbaaa → baaaa → b
Для данной строки напишите программу чтобы решить, можно ли превратить строку в пустую строку с помощью некоторой последовательности операций извлечения.

Подробнее здесь: https://stackoverflow.com/questions/792 ... ates-occur