Overview

This is a problem where you remove adjacent identical characters two at a time, and you need to find the minimum possible length of the remaining string. This problem can be solved in \(O(|S|)\) by scanning the string from left to right and managing the “characters that remain undeleted” with a stack.

Analysis

The operation allows you to remove two adjacent identical characters. For example, with abba:

• abba
• Remove bb to get aa
• Remove aa to get an empty string

So the final length is \(0\).

Key Insight

When scanning characters from left to right, the only character that a newly seen character c can potentially cancel with is the rightmost character currently remaining.

This is because if we maintain the state where “everything that could be cancelled has already been cancelled” for the characters processed so far, the only character that can be adjacent to the new character c is the last character of what remains.

Worked Example

Let’s process abbaca from left to right:

• See a → remaining: a
• See b → remaining: ab
• See b → last character is also b, so remove it → remaining: a
• See a → last character is also a, so remove it → remaining: empty
• See c → remaining: c
• See a → last character is c, can’t remove → remaining: ca

The final length is \(2\).

Why the Naive Approach Doesn’t Work

One might consider scanning the entire string each time to find and delete pairs like aa or bb. However, if you rebuild and re-scan the string after each deletion, it takes \(O(|S|^2)\) in the worst case.

Since \(|S| \le 10^6\) in this problem, this approach is too slow.

How to Solve It

We maintain a stack representing “the string after cancelling as much as possible from the portion processed so far.”

Each time we read a new character c:

• If the top of the stack is c, they form an adjacent pair of identical characters, so we pop to cancel them
• Otherwise, we push c onto the stack

By repeating this, we always maintain the “minimal form up to the current position.”

Algorithm

1. Prepare an empty stack.
2. Scan the string \(S\) one character at a time from left to right.
3. Let the current character be c.
   • If the stack is non-empty and the top of the stack equals c, instead of removing two characters, pop one character from the stack.
   • Otherwise, append c to the stack.
4. The number of characters remaining in the stack at the end is the answer.

Why This Is Correct

At each point, the stack contains “the string that remains after performing as many operations as possible on the substring from the beginning up to the current position.”

When a new character c is added:

• If the top is c, those two characters are currently adjacent, so they can be removed
• If the top is not c, then c cannot be removed at this point, so it must stay

In other words, the greedy decision at each step is always optimal. By performing this process to the end, we obtain the minimum remaining length for the entire string.

Complexity

• Time complexity: \(O(|S|)\)
• Space complexity: \(O(|S|)\)

Each character is pushed onto the stack at most once and popped at most once, so the overall time is linear.

Implementation Notes

In Python, using a list as a stack is the standard approach.

• stack.append(c) to push
• stack.pop() to pop
• stack[-1] to peek at the top

In this problem, since the string length can be up to \(10^6\), it is safer to use sys.stdin.readline().strip() for input.

Source Code

import sys

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))

---

This editorial was generated by gpt-5.4-high.