超定番の stack を使うやつですね。類題として

がある。これらは見た目は違えど、どれも

(()((()())()())())()))(())

のようなカッコ列の整合性に関する問題だ。カッコ列の整合性には以下のような超定番の判定方法がある:

stack を用意する
左カッコが来たら stack に追加
右カッコが来た時、stack が空だったら「不整合エラー検出」で空じゃなかったら stack にある左カッコと今ある右カッコとをペアにして stack から pop する

こうして最後までやったとき、stack が空なら「整合」していて、stack が空じゃなかったら「不整合」になる。不整合のパターンは

途中で stack が空なのに右カッコが来る
最後に stack に左カッコがあまる

の 2 つがある。

AGC 005 A - STring 問題へのリンク

問題概要

S と T のみで構成された列が与えられる。

文字列中に "ST" のペアがあったら、そのうち一番左にあるものを消す

という操作を繰り返す。最後に残る文字列の長さを求めよ。

制約

1 <= 文字列長 <= 10⁵

解法

冒頭に述べたような stack 処理を行う。修正点として

stack が空のときに右カッコが来たら構わず無視

とする。pop される回数をカウントしておいてそれを x とすると答えは「(元の文字列長) - 2x」になる。

なお実装上は、stack は陽に持たず、単純に「左カッコの個数」をカウントするカウンター変数を持っておくだけでよい。

#include <iostream>
#include <string>
using namespace std;

int main() {
  string X; cin >> X;
  int stack = 0, puyo = 0;
  for (int i = 0; i < (int)X.size(); ++i) {
    if (X[i] == 'S') ++stack;
    else if (stack > 0) --stack, ++puyo;
  }
  cout << (int)X.size() - puyo*2 << endl;
}