A - STring 解説 /

実行時間制限: 1 sec / メモリ制限: 256 MB

配点 : 300 点

問題文

文字列 X が与えられます。X の長さは偶数であり、半分は S 、もう半分は T からなります。

高橋君は ST という文字列が苦手です。なので以下の操作を 10^{10000} 回行うことにしました。

  • X の(連続な)部分文字列で ST となるもののうち、最も左側にあるものを取り除く。存在しないならば何もしない。

最終的に X は何文字になるかを求めてください。

制約

  • 2 ≦ |X| ≦ 200,000
  • X の長さは偶数
  • X を構成する文字のうち半分は S であり、もう半分は T である

部分点

  • 200 点分のデータセットでは |X| ≦ 200 が成り立つ

入力

入力は以下の形式で標準入力から与えられる。

X

出力

1 行に問題の答えを出力する。

入力例 1

TSTTSS

出力例 1

4

1 回目の操作では TSTTSS の 2,3 文字目が ST なので取り除きます。 X は TTSS になり、もう ST はないため残り 10^{10000}-1 回は何もしません。 よって答えは 4 となります。

入力例 2

SSTTST

出力例 2

0

SSTTST ⇒ STST ⇒ ST ⇒ `` となり、最終的に空文字列になります。

入力例 3

TSSTTTSS

出力例 3

4

TSSTTTSS ⇒ TSTTSS ⇒ TTSS となります。

Score : 300 points

Problem Statement

We have a string X, which has an even number of characters. Half the characters are S, and the other half are T.

Takahashi, who hates the string ST, will perform the following operation 10^{10000} times:

  • Among the occurrences of ST in X as (contiguous) substrings, remove the leftmost one. If there is no occurrence, do nothing.

Find the eventual length of X.

Constraints

  • 2 ≦ |X| ≦ 200,000
  • The length of X is even.
  • Half the characters in X are S, and the other half are T.

Partial Scores

  • In test cases worth 200 points, |X| ≦ 200.

Input

The input is given from Standard Input in the following format:

X

Output

Print the eventual length of X.

Sample Input 1

TSTTSS

Sample Output 1

4

In the 1-st operation, the 2-nd and 3-rd characters of TSTTSS are removed. X becomes TTSS, and since it does not contain ST anymore, nothing is done in the remaining 10^{10000}-1 operations. Thus, the answer is 4.

Sample Input 2

SSTTST

Sample Output 2

0

X will eventually become an empty string: SSTTST ⇒ STST ⇒ ST ⇒ ``.

Sample Input 3

TSSTTTSS

Sample Output 3

4

X will become: TSSTTTSS ⇒ TSTTSS ⇒ TTSS.