A warehouse conveyor belt carries a single-file line of package tags, each stamped with one uppercase English letter. A scanning arm continuously watches the belt and, whenever two tags sitting immediately next to each other spell exactly AB or exactly CD (read left to right), it yanks that adjacent pair off the belt; the belt then closes the gap, which may bring two previously separated tags together and trigger further removals. This process repeats until no adjacent pair anywhere on the belt spells AB or CD.
Given the original sequence of tags, determine how many tags remain once the scanning arm can find nothing left to remove.
A single line containing the string s of uppercase English letters describing the tags on the belt, in order from the front of the line to the back.
Print a single integer: the number of tags remaining after all possible removals have taken place.
s ≤ 10^5s consists only of uppercase English letters A–ZExample 1
Input
ABFCACDB
Expected
2
Explanation
Scanning left to right with a stack: A is pushed. B arrives and the top is A, so A and B cancel (stack empty). F is pushed. C is pushed. A is pushed (top is now C, no match). C is pushed (top is A, no match). D arrives and the top is C, so C and D cancel, leaving stack [F, C, A]... continuing, the next tag is B, and the top is A, so A and B cancel, leaving [F, C]. No more cancellations are possible, so 2 tags remain.
Example 2
Input
ACBBD
Expected
5
Explanation
A is pushed. C is pushed (top A, no match). B arrives; the top is C, not A, so no cancellation — B is pushed. Another B arrives; the top is B, not A, so no cancellation — it is pushed too. D arrives; the top is B, not C, so no cancellation — it is pushed. No adjacent 'AB' or 'CD' pair ever forms, so all 5 tags remain.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →