AGC005 A - STring

問題

'S'と'T'からなる文字列Xがある。文字列のうち左から"ST"があればそれを繰り返し削除する。最後に残る文字数を答えよ。

  • 2\le |X| \le 200000

解法

左から見て'S'が来た回数だけ'T'を削除できると考えればO(n)で解ける。

int main() {
  int cnt{0}, size{0}, ans{0};
  for(char c; ~scanf("%c", &c) && c != '\n'; size++) {
    if(c == 'S') cnt++;
    else if(cnt > 0) cnt--, ans++;
  }
  cout << size - 2 * ans << endl;
  return 0;
}