

Time Limit: 1 sec / Memory Limit: 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 areT
.
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
.