分数: 300 点
问题陈述
我们有一个字符串 X,其字符数为偶数。一半的角色是 S,另一半是 T.
高桥,讨厌字符串 ST,将执行以下操作 10^{10000} 次:
- 出现以下情况
STin X 作为(连续)子字符串,删除最左边的一个。如果没有发生,则不执行任何操作。
找到最终的长度 X.
约束
- 2 ≦ |X| ≦ 200,000
- 的长度 X 是偶数。
- 中的一半字符 X 是
S,另一半是T.
部分分数
- 在测试用例中值得 200 点, |X| ≦ 200.
输入
输入由标准输入按以下格式给出:
X
输出
打印最终长度 X.
示例输入 1
TSTTSS
示例输出 1
4
在 1-st 操作, 2-nd 和 3-rd 字符 TSTTSS 被删除。
X 变为 TTSS,并且由于它不包含 ST 不再了,剩下的时间里什么也没做 10^{10000}-1 操作。
因此,答案是 4.
示例输入 2
SSTTST
示例输出 2
0
X 最终会变成空字符串: SSTTST ⇒ STST ⇒ ST ⇒ ``.
示例输入 3
TSSTTTSS
示例输出 3
4
X 将变为: TSSTTTSS ⇒ TSTTSS ⇒ TTSS.