Collapse Letter Pairs

Easy

You get a string text made of uppercase English letters. Whenever an A is immediately followed by a B, or a C is immediately followed by a D, you may strike that pair out, and the remaining parts of the string close up. Closing up can create new such pairs, and those may be struck out as well. You may strike out pairs as many times as you like and in any order. Return the smallest length the string can be reduced to.

Example 1

text='CABDX' → 1

First AB vanishes and the string becomes CDX; now C and D are neighbours and vanish too, leaving X of length 1.

Example 2

text='BADC' → 4

The letters come in reverse order (BA, DC), which does not count, so the length stays 4.

Example 3

text='ACDBCD' → 0

ACDBCD → ABCD → CD → the empty string.

Constraints

1 ≤ len(text) ≤ 10⁵
text contains only uppercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Stack String Simulation

Similar problems

Same Text After Erasing Easy Digits as Backspace Easy Erase the Pattern Until It Is Gone Medium Crashes on One Lane Medium Star as Backspace Medium

Input

text='CABDX'

Expected

Run checks the first 3 tests in your browser. Submit checks all 155 tests on the server, hidden ones included.