概要

隣り合う同じ文字を 2 文字ずつ消していく操作を、最終的な文字列長が最小になるように行う問題です。
この問題は「左から順に見て、直前の未消去文字と同じなら打ち消す」という処理をスタックで実装すると、最小長を一度の走査で求められます。

考察

重要な観察は次の 2 つです。

1. 消せるのは「隣り合う同じ文字」だけ
   
2. ある文字を見たとき、影響するのは「現在の末尾（直前に残っている文字）」だけ

例えば abba を考えると：

• a を残す → a
• b を残す → ab
• 次の b は末尾 b と同じなので 2 つ消える → a
• 次の a は末尾 a と同じなので 2 つ消える → 空

最終的に長さ 0 です。

---

素朴に「消せる場所を毎回探して削除」を繰り返すと、
1 回の削除ごとに探索と文字列再構築が発生し、最悪で \(O(N^2)\) 近くになります。
\(|S| \le 10^6\) なのでこれは間に合いません。

そこで、スタックを使います。

• 文字を左から 1 つずつ処理
• スタック先頭（末尾）と同じ文字なら pop（2文字が相殺）
• 違うなら append（未確定として残す）

この方法だと、各文字は高々 1 回 push / 1 回 pop されるだけなので高速です。
また、この処理は「実際に削除を最適に繰り返した結果」と一致します。

アルゴリズム

1. 空のスタック stack を用意する。
2. 文字列 S を左から順に文字 c について見る。
   • stack が空でなく、stack[-1] == c なら stack.pop() する。
   • それ以外なら stack.append(c) する。
3. 全文字処理後、len(stack) を出力する。

具体例 abccbd：

• a → [a]
• b → [a,b]
• c → [a,b,c]
• c（同じ）→ [a,b]
• b（同じ）→ [a]
• d → [a,d]

最終長は 2。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

（\(N = |S|\)）

実装のポイント

• Python ではリストをスタックとして使い、append / pop で十分高速です。

• 入力サイズが大きいので sys.stdin.readline().strip() を使うのが安全です。

• 出力は長さだけなので print(len(stack)) で完了します。

  ソースコード

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

---

この解説は gpt-5.3-codex によって生成されました。