B - Organizing Strings Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 333 点

問題文

高橋君は、文字列を整理する作業をしています。

高橋君は、文字列に対して次の操作を 0 回以上繰り返し行うことができます。

  • 文字列の中から、隣り合う同じ文字 2 文字（例えば aa や bb）を 1 組選び、その 2 文字を文字列から取り除く。取り除いた後、残った左右の部分はそのまま連結される。

例えば、文字列 abba に対して、隣り合う bb を取り除くと aa になり、さらに aa を取り除くと空文字列になります。

英小文字からなる文字列 S が与えられるので、操作を繰り返した後に得られる文字列の長さの最小値を求めてください。

制約

  • 1 \leq |S| \leq 10^6（|S| は文字列 S の長さを表す）
  • S は英小文字からなる文字列である。

入力

S

文字列 S が 1 行で与えられる。

出力

操作を最適に繰り返した後に得られる文字列の長さの最小値を 1 行で出力せよ。

入力例 1

abba

出力例 1

0

入力例 2

abcde

出力例 2

5

入力例 3

abbacaaccbbddeeffeedcba

出力例 3

5

入力例 4

aaabccddddeeffffggghhhiiijjjkkklllmmmnnnooopppqqqrrrssstttuuuvvvwwwxxxyyyzzz

出力例 4

22

入力例 5

a

出力例 5

1

Score : 333 pts

Problem Statement

Takahashi is working on organizing strings.

Takahashi can perform the following operation on a string zero or more times:

  • Choose one pair of adjacent identical characters (for example, aa or bb) in the string, and remove those 2 characters from the string. After removal, the remaining left and right parts are concatenated as they are.

For example, given the string abba, removing the adjacent bb yields aa, and further removing aa yields the empty string.

You are given a string S consisting of lowercase English letters. Find the minimum possible length of the string obtained after performing the operation repeatedly.

Constraints

  • 1 \leq |S| \leq 10^6 (|S| denotes the length of string S)
  • S is a string consisting of lowercase English letters.

Input

S

The string S is given on a single line.

Output

Print the minimum possible length of the string obtained after optimally repeating the operation, on a single line.

Sample Input 1

abba

Sample Output 1

0

Sample Input 2

abcde

Sample Output 2

5

Sample Input 3

abbacaaccbbddeeffeedcba

Sample Output 3

5

Sample Input 4

aaabccddddeeffffggghhhiiijjjkkklllmmmnnnooopppqqqrrrssstttuuuvvvwwwxxxyyyzzz

Sample Output 4

22

Sample Input 5

a

Sample Output 5

1