Minimum String Length After Removing Substrings

easyGreedyhashingmonotonic stacks

You are given a string $$$s$$$ consisting only of uppercase English letters. In one operation, you may remove any occurrence of the substring "AB" or "CD" from $$$s$$$.

After removal, the remaining parts of the string concatenate, which may create new occurrences of "AB" or "CD".

Determine the minimum possible length of the string after applying zero or more such operations optimally.

Input Format:

A single line containing the string $$$s$$$.

  • $$$1 \le |s| \le 100000$$$.
  • $$$s$$$ contains only the characters A–Z.

Output Format:

Print a single integer: the minimum length of the string obtainable after performing the removals.

Examples:

Example 1:

Input:

AXBYCDZC

Output:

6

Example 2:

Input:

ACABDB

Output:

0

Note:

In the first testcase,

  • We start with the string "AXBYCDZC".
  • We remove "CD" from AXBYCDZC, and the parts left behind join together. The string becomes "AXBYZC".
  • There are no more "AB" or "CD" pairs. Thus, the final string is "AXBYZC", which has a length of 6.

In the second testcase,

  • We start with the string "ACABDB".
  • Remove AB from ACABDB. The string becomes ACDB.
  • Remove CD from ACDB. The string becomes AB.
  • Remove AB from AB. The string becomes empty. The final length is 0.

Code

Loading Editor...