分数: 333 分
问题陈述
Takahashi 正在致力于组织字符串。
Takahashi 可以对字符串执行以下操作零次或多次:
- 选择一对相邻的相同字符(例如,
aaorbb)在字符串中,并删除那些 字符串中的 2 个字符。移除后,剩余的左右部分按原样连接起来。
例如,给定字符串 abba,删除相邻的 bb 产量 aa,并进一步删除 aa 产生空字符串。
给你一个字符串 S 由小写英文字母组成。求重复执行操作后得到的字符串的最小可能长度。
约束
- 1 \leq |S| \leq 10^6 (|S| 表示字符串的长度 S)
- S 是由小写英文字母组成的字符串。
输入
S
字符串 S 在一行中给出。
输出
在一行上打印最佳重复操作后获得的字符串的最小可能长度。
示例输入 1
abba
示例输出 1
0
示例输入 2
abcde
示例输出 2
5
示例输入 3
abbacaaccbbddeeffeedcba
示例输出 3
5
示例输入 4
aaabccddddeeffffggghhhiiijjjkkklllmmmnnnooopppqqqrrrssstttuuuvvvwwwxxxyyyzzz
示例输出 4
22
示例输入 5
a
示例输出 5
1