概要

隣り合う同じ文字を 2 文字ずつ消していくとき、最終的に残る文字列の長さの最小値を求める問題です。
この問題は、文字列を左から順に見ながら「消えずに残っている文字」をスタックで管理すると、\(O(|S|)\) で解けます。

考察

操作では、隣り合う同じ文字 2 つを取り除けます。
例えば abba なら、

• abba
• bb を消して aa
• aa を消して空文字列

となり、最終的な長さは \(0\) です。

重要な気づき

ある文字を左から順に見ていくとき、新しく見た文字 c が消える可能性があるのは、今の時点で一番右に残っている文字だけです。

なぜなら、途中の文字たちはすでに「消せるものは消した」状態にしておけば、新しい文字 c と隣り合う可能性があるのは、その残りの末尾だけだからです。

例で考える

例えば abbaca を左から処理してみます。

• a を見る → 残り: a
• b を見る → 残り: ab
• b を見る → 末尾も b なので消す → 残り: a
• a を見る → 末尾も a なので消す → 残り: 空
• c を見る → 残り: c
• a を見る → 末尾は c なので消せない → 残り: ca

最終的な長さは \(2\) です。

素朴な方法がだめな理由

毎回文字列全体を見て、aa や bb などを探して削除する、という方法も考えられます。
しかし、1 回削除するたびに文字列を詰め直して再探索すると、最悪で \(O(|S|^2)\) かかります。

今回は \(|S| \le 10^6\) なので、この方法では間に合いません。

どう解決するか

「今までに処理した部分の、消せるだけ消した後の文字列」をスタックで持ちます。

新しい文字 c を読むたびに：

• スタックの一番上が c なら、隣り合う同じ文字になるので pop して消す
• そうでなければ push して残す

これを繰り返せば、常に「ここまでの最小形」を保てます。

アルゴリズム

1. 空のスタックを用意する。
2. 文字列 \(S\) を左から 1 文字ずつ見る。
3. 現在の文字を c とする。
   • スタックが空でなく、かつスタックの先頭（末尾）が c と同じなら、2 文字を消す代わりにスタックから 1 文字 pop する。
   • そうでなければ、c をスタックに append する。
4. 最後にスタックに残っている文字数が答え。

なぜこれで正しいか

各時点でスタックには、「先頭からそこまでの部分文字列に対して、可能な限り操作をした後に残る文字列」が入っています。

新しい文字 c を追加したとき、

• 末尾が c なら、その 2 文字は今まさに隣り合っているので消せます
• 末尾が c でないなら、c は今の時点では消せないので残すしかありません

つまり、その場での判断が常に最適です。
この処理を最後まで行えば、文字列全体に対する最小の残り長さが得られます。

計算量

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

各文字はスタックに高々 1 回 push され、高々 1 回 pop されるだけなので、全体で線形時間です。

実装のポイント

Python では、リストをスタックとして使うのが定番です。

• stack.append(c) で積む
• stack.pop() で取り出す
• stack[-1] で一番上を確認する

今回のコードでは、文字列長が最大 \(10^6\) と大きいため、入力は sys.stdin.readline().strip() を使うと安全です。

ソースコード

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

---

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