Overview

This is a problem where you repeatedly remove pairs of adjacent identical characters, aiming to minimize the final string length. This problem can be solved by implementing the following process with a stack: “scan from left to right, and if the current character matches the most recent unremoved character, cancel them out.” This yields the minimum length in a single pass.

Analysis

The two key observations are:

1. You can only remove “adjacent identical characters”
2. When looking at a character, the only thing that matters is “the current tail (the most recently remaining character)”

For example, consider abba:

• Keep a → a
• Keep b → ab
• The next b matches the tail b, so both are removed → a
• The next a matches the tail a, so both are removed → empty

The final length is 0.

---

A naive approach of “repeatedly finding a removable pair and deleting it” would require searching and string reconstruction for each deletion, leading to \(O(N^2)\) in the worst case. Since \(|S| \le 10^6\), this is too slow.

Instead, we use a stack.

• Process characters one by one from left to right
• If the top of the stack matches the current character, pop (the two characters cancel out)
• Otherwise, append (keep it as undecided)

With this approach, each character is pushed at most once and popped at most once, making it efficient. Moreover, this process produces the same result as optimally repeating the actual deletions.

Algorithm

1. Prepare an empty stack stack.
2. Iterate through string S from left to right, examining each character c:
   • If stack is not empty and stack[-1] == c, then stack.pop().
   • Otherwise, stack.append(c).
3. After processing all characters, output len(stack).

Concrete example abccbd:

• a → [a]
• b → [a,b]
• c → [a,b,c]
• c (same) → [a,b]
• b (same) → [a]
• d → [a,d]

The final length is 2.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

(\(N = |S|\))

Implementation Notes

• In Python, using a list as a stack with append / pop is sufficiently fast.

• Since the input size can be large, it is safer to use sys.stdin.readline().strip().

• Since we only need to output the length, print(len(stack)) is all that’s needed.

  Source Code

import sys

def main():
    s = sys.stdin.readline().strip()
    stack = []
    for c in s:
        if stack and stack[-1] == c:
            stack.pop()
        else:
            stack.append(c)
    print(len(stack))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.3-codex.