概要

与えられた文字列から「隣り合う同じ2文字を削除する」という操作を、これ以上できなくなるまで繰り返したときの最終的な文字列の長さを求める問題です。

考察

この問題のポイントは、あるペアを削除したことによって、それまで離れていた文字同士が新たに隣り合い、さらに削除できる可能性があるという点です。

例えば、文字列 abba を考えてみます。 1. まず、中央の bb を削除します。 2. すると、残った左の a と右の a が隣り合い、aa となります。 3. この aa も削除できるため、最終的には空文字列（長さ 0）になります。

このように、削除によって状況が連鎖的に変化するため、単純に前から順番に消していくだけでは不十分に見えるかもしれません。しかし、「今見ている文字」と「直前に残した文字」を比較し、同じであれば取り除くという処理を繰り返すことで、効率的に解くことができます。

もし、愚直に「文字列の中から同じ文字のペアを探して削除し、文字列を連結し直す」という処理を繰り返すと、1回の削除に \(O(N)\) かかり、全体で最大 \(O(N^2)\) の時間がかかってしまいます。制約の \(|S| \leq 10^6\) では、より効率的な手法が必要です。

アルゴリズム

スタック（Stack）というデータ構造を使うことで、この問題を \(O(N)\) で解くことができます。

1. 空のスタックを用意します。
2. 文字列 \(S\) を先頭から 1 文字ずつ順番に見ていきます（現在の文字を char とします）。
   • スタックが空でなく、かつスタックの最上位（最後に追加した文字）が char と同じである場合：
     • 隣り合う同じ文字のペアが見つかったことになります。この文字は最終的な文字列には残らないため、スタックの最上位を削除（pop）します。
   • そうでない場合（スタックが空、または文字が異なる場合）：
     • その文字をスタックに追加（push）します。
3. すべての文字を処理し終えたとき、スタックに残っている文字が「最終的に残る文字列」です。その数（スタックのサイズ）を出力します。

この方法では、各文字を 1 回ずつチェックするだけで済み、削除によって新しく隣り合うことになった文字同士も、スタックの性質によって正しく判定できます。

計算量

• 時間計算量: \(O(|S|)\) 文字列を 1 回走査し、各文字に対してスタックへの追加・削除を最大 1 回ずつ行うため、文字数に比例した時間で終わります。
• 空間計算量: \(O(|S|)\) 最悪の場合（削除できるペアが 1 つもない場合）、スタックにすべての文字を格納するためです。

実装のポイント

• Python ではリストをスタックとして代用できます。末尾への追加は append()、末尾の削除は pop() を使用します。

• スタックが空の状態で stack[-1]（末尾の参照）を行うとエラーになるため、必ず if stack: などでスタックが空でないことを確認してから比較を行うようにしましょう。

  ソースコード

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

この解説は gemini-3-flash-thinking によって生成されました。