Overview

This is a problem where, given a string, you repeatedly perform the operation “delete two adjacent identical characters” until no more such operations can be performed, and find the length of the final string.

Analysis

The key point of this problem is that deleting a pair can cause previously separated characters to become newly adjacent, potentially enabling further deletions.

For example, consider the string abba. 1. First, delete the central bb. 2. Then, the remaining left a and right a become adjacent, forming aa. 3. Since this aa can also be deleted, the final result is an empty string (length 0).

Because deletions can trigger chain reactions like this, it might seem insufficient to simply scan and delete from left to right. However, by comparing “the current character” with “the most recently kept character” and removing them if they match, we can solve this efficiently.

If we naively repeat the process of “finding a pair of identical characters in the string, deleting them, and reconstructing the string,” each deletion takes \(O(N)\) time, resulting in up to \(O(N^2)\) total time. Given the constraint \(|S| \leq 10^6\), a more efficient approach is needed.

Algorithm

By using a data structure called a Stack, we can solve this problem in \(O(N)\).

1. Prepare an empty stack.
2. Iterate through the string \(S\) one character at a time from the beginning (let the current character be char).
   • If the stack is not empty and the top of the stack (the most recently added character) is the same as char:
     • This means we have found a pair of adjacent identical characters. Since these characters will not remain in the final string, pop the top of the stack.
   • Otherwise (the stack is empty, or the characters differ):
     • Push the character onto the stack.
3. After processing all characters, the characters remaining in the stack form the “final remaining string.” Output its count (the size of the stack).

With this method, we only need to check each character once, and thanks to the properties of the stack, characters that become newly adjacent after a deletion are correctly handled.

Complexity

• Time complexity: \(O(|S|)\) We scan the string once, performing at most one push and one pop per character, so the time is proportional to the number of characters.
• Space complexity: \(O(|S|)\) In the worst case (when there are no deletable pairs), all characters are stored in the stack.

Implementation Notes

• In Python, a list can be used as a stack. Use append() to add to the end and pop() to remove from the end.

• Accessing stack[-1] (referencing the last element) when the stack is empty will cause an error, so always check that the stack is not empty with something like if stack: before making the comparison.

  Source Code

import sys

def solve():
    # 入力を取得
    s = sys.stdin.readline().strip()
    
    # スタックを用いて隣り合う同じ文字を処理する
    stack = []
    for char in s:
        # スタックのトップと同じ文字が来た場合、ペアを取り除く（スタックからポップする）
        if stack and stack[-1] == char:
            stack.pop()
        else:
            # 異なる文字、またはスタックが空の場合は追加する
            stack.append(char)
    
    # 残った文字数が最小の長さ
    print(len(stack))

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.