概要

文字列から「隣り合う同じ文字のペア」を繰り返し取り除いたとき、最終的に残る文字列の長さの最小値を求める問題です。スタックを使うことで効率的に解くことができます。

考察

重要な気づき：取り除く順番は結果に影響しない

まず、どの順番でペアを取り除いても、最終的に残る文字列は同じになるという重要な性質があります。

例えば abba の場合： - bb を取り除く → aa → aa を取り除く → 空文字列（長さ \(0\)）

これは、括弧の対応付け問題に似た構造を持っています。

素朴なアプローチの問題点

素朴に「文字列を走査してペアを見つけたら取り除き、先頭からやり直す」方法を考えると、最悪の場合、取り除くたびに文字列全体を再走査する必要があり、\(O(|S|^2)\) の時間がかかります。\(|S|\) が最大 \(10^6\) なので、これでは TLE になる可能性があります。

スタックによる解決

文字列を左から1文字ずつ見ていくとき、スタックを使えば一度の走査で解決できます。

• 今見ている文字がスタックの一番上の文字と同じなら、隣り合う同じ文字のペアが見つかったことになるので、スタックから取り除きます（ペアを消去）。
• 異なるなら、スタックに積みます。

ペアを消去した結果、新たに隣り合う文字同士が同じになる場合も、スタックの構造により自然に処理されます。

アルゴリズム

具体例で動きを見てみましょう。文字列 abbaca の場合：

読む文字	スタックの状態	操作
a	[a]	スタックが空なので積む
b	[a, b]	先頭 a ≠ b なので積む
b	[a]	先頭 b = b なのでポップ（ペア消去）
a	[]	先頭 a = a なのでポップ（ペア消去）
c	[c]	スタックが空なので積む
a	[c, a]	先頭 c ≠ a なので積む

最終的にスタックには [c, a] が残り、答えは 2 です。

このように、ペアを消した後に新たに隣り合った文字（上の例では2つの a）も自動的にペアとして検出・消去されます。

計算量

• 時間計算量: \(O(|S|)\) — 文字列を1回走査するだけで、各文字に対する操作（push または pop）は \(O(1)\) です。
• 空間計算量: \(O(|S|)\) — 最悪の場合（ペアが一つも消えない場合）、スタックに全文字が入ります。

実装のポイント

• Python のリストは append と pop が \(O(1)\) で動作するため、スタックとしてそのまま利用できます。

• stack and stack[-1] == c の stack and 部分は、スタックが空のときに stack[-1] へアクセスしてエラーになるのを防ぐ短絡評価です。スタックが空なら False となり、後半の比較は実行されません。

• 最終的な答えはスタックに残った要素数、すなわち len(stack) です。

  ソースコード

S = input()
stack = []
for c in S:
    if stack and stack[-1] == c:
        stack.pop()
    else:
        stack.append(c)
print(len(stack))

---

この解説は claude4.6opus-thinking によって生成されました。