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

[Anonymous]

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

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

def can_reduce_to_empty(s):
stack = []
while True:
n = len(s)
i = 0
new_s = []

while i < n:
char = s[i]
# Count consecutive occurrences
count = 1
while i + 1 < n and s[i + 1] == char:
count += 1
i += 1

# If the group has 2 or more consecutive occurrences, don't add it to new_s
print(f"left overs: {new_s}")
if count < 2:
new_s.append(char)

i += 1

# Join the new string after processing
s = ''.join(new_s)

# If the string has not changed, break out of the loop
if len(s) == n:
break

# If the string becomes empty, return True
return 1 if len(s) == 0 else 0

# Input and output handling
def main():
T = int(input().strip())  # Number of test cases
results = []
for _ in range(T):
s = input().strip()  # Input string for each test case
results.append(can_reduce_to_empty(s))
print("\n".join(map(str, results)))

# Run the main function
if __name__ == "__main__":
main()

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

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