[Python] Checking if a string of "a" and "b" can be reduced to empty if duplicates occur...

I'm trying to approach this issue with O(n) so I'm using a stack. In this code:

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

while i < n:
char = s
# 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()


The problem is I'm getting an output 0 when it should be 1

I tried using a matrix which did result in the same issue, so I'm guessing its a logic error?

Context: We are given a string s of two characters 'a' and 'b' Let a group be a maximal consecutive substring of the same character. Any group g of s of length at least two can be removed (or popped) and a new string is constructed by concatenating the remaining left and right substrings of s. We repeat this process until either the string becomes the empty string or there is no more group of length at least two. For example, string s = babbbaaabb has 5 groups b, a, bbb, aaa, and bb. The string s can be turned into the empty string by popping groups in the following sequence (the group in italics is to be popped in the sequence):

babbbaaabb → baaaabb → bbb → empty string

But the group may not turn to an empty string by a different sequence of pop operations:

babbbaaabb → babbbaaa → baaaa → b

Given a string, write a program to decide whether the string can be turned into the empty string by some sequence of popping operations.

Continue reading...