Overview

This problem asks you to find the minimum length of the string that remains after repeatedly removing “pairs of adjacent identical characters” from a string. It can be solved efficiently using a stack.

Analysis

Key Insight: The order of removal does not affect the result

First, there is an important property: no matter what order you remove pairs in, the final remaining string is always the same.

For example, with abba: - Remove bb → aa → Remove aa → empty string (length \(0\))

This has a structure similar to the bracket matching problem.

Problems with the naive approach

If we naively “scan the string, find a pair, remove it, and restart from the beginning,” in the worst case we would need to rescan the entire string after each removal, resulting in \(O(|S|^2)\) time. Since \(|S|\) can be up to \(10^6\), this could result in TLE.

Solution using a stack

When scanning the string one character at a time from left to right, we can solve it in a single pass using a stack.

• If the current character is the same as the character on top of the stack, a pair of adjacent identical characters has been found, so we pop it from the stack (removing the pair).
• If they are different, we push the current character onto the stack.

Even when removing a pair causes new adjacent characters to become identical, the stack structure naturally handles this.

Algorithm

Let’s trace through a concrete example. For the string abbaca:

Character read	Stack state	Operation
a	[a]	Stack is empty, so push
b	[a, b]	Top a ≠ b, so push
b	[a]	Top b = b, so pop (pair removed)
a	[]	Top a = a, so pop (pair removed)
c	[c]	Stack is empty, so push
a	[c, a]	Top c ≠ a, so push

In the end, the stack contains [c, a], and the answer is 2.

As shown, after removing a pair, newly adjacent characters (the two as in the example above) are automatically detected and removed as a pair.

Complexity

• Time complexity: \(O(|S|)\) — We only scan the string once, and each operation per character (push or pop) is \(O(1)\).
• Space complexity: \(O(|S|)\) — In the worst case (when no pairs are removed), all characters are stored in the stack.

Implementation Notes

• Python lists have \(O(1)\) append and pop operations, so they can be used directly as a stack.

• The stack and part in stack and stack[-1] == c is short-circuit evaluation that prevents an error from accessing stack[-1] when the stack is empty. If the stack is empty, it evaluates to False, and the comparison in the latter half is not executed.

• The final answer is the number of elements remaining in the stack, i.e., len(stack).

  Source Code

S = input()
stack = []
for c in S:
    if stack and stack[-1] == c:
        stack.pop()
    else:
        stack.append(c)
print(len(stack))

---

This editorial was generated by claude4.6opus-thinking.