実は、以下のアルゴリズムで長さが最小となる操作後の文字列の一例を得ることができます。

• 答え \(T\) を空文字列で初期化する。
• \(i=1,2,\dots,|S|\) について、以下を繰り返す。
  • \(T\) が空であるか、 \(T\) の末尾と \(S\) の \(i\) 文字目が異なるとき、 \(T\) の末尾に \(S\) の \(i\) 文字目を追加する。
  • そうでないとき、 \(T\) の末尾の文字を削除する。

証明:

以下の事項を証明することで、上記のアルゴリズムの正当性を証明します。

• 文字列内に同一の文字が隣接しているとき、それらを直ちに削除しても到達できる文字列の最小長は変わらない。

文字列の最小長を達成する操作列をひとつ取ってきたと仮定し、その操作列を使ったときについて、ある同一文字の連続 \(c_1c_2\) に着目します。
これらの双方を消さない場合は明らかに文字列の長さが最小とはならないので、どちらかは消していることになり、以降はこの場合について考えます。
もし \(c_1,c_2\) を組にして消さなかった(別のペアを作った)場合、 \(c_1,c_2\) どちらかとその相方とを先に消すことになります(この相方を \(c_x\) とします)。
しかしながら、その時点で \(\dots c_1c_2c_x \dots\) あるいは \(\dots c_xc_1c_2 \dots\) という状況になっており、このとき \(c_x\) とどちらかとを組む代わりに \(c_1\) と \(c_2\) とを組んでも結果は変わりません。
よって、上記の事項が証明されました。

また、上記のアルゴリズムについて \(T\) 中で同じ文字が連続することはないため、これ以上操作を行うことができない状態を得ることができています。

本解法の時間計算量は \(O(|S|)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  string S;
  cin >> S;
  string T;
  for(auto &nx : S){
    if(T.empty() || T.back()!=nx){T.push_back(nx);}
    else{T.pop_back();}
  }
  cout << T.size() << "\n";
  return 0;
}