← 返回题目列表

AtCoder · awc0109_b

B. 组织字符串

中文机器翻译题面 查看原题

分数: 333 分

问题陈述

Takahashi 正在致力于组织字符串。

Takahashi 可以对字符串执行以下操作零次或多次:

  • 选择一对相邻的相同字符(例如, aa or bb)在字符串中,并删除那些 字符串中的 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