Minimize String Length by Deleting AB and BB Pairs
Company: J.P. Morgan
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Online Assessment
Given a string `seq` containing only `A` and `B`, you may repeatedly delete either adjacent substring `AB` or adjacent substring `BB`.
After each deletion, concatenate the remaining prefix and suffix. Characters that were separated may become adjacent and form another deletable pair. Return the minimum possible length after any number of valid deletions, including zero deletions.
### Input and Output
- Input: the string `seq`.
- Output: one integer, the minimum remaining length over all valid deletion sequences.
### Constraints
- `1 <= len(seq) <= 200000`.
- Every character of `seq` is either `A` or `B`.
- A pair must be adjacent at the time it is deleted.
### Example
```text
seq = "BABBA"
answer = 1
```
Deleting the `AB` beginning at zero-based index `1` gives `BBA`. Deleting its leading `BB` then leaves `A`.
Overview: Find the minimum remaining length of an A/B string after repeatedly deleting adjacent AB or BB pairs and joining the remaining characters.
Read the full J.P. Morgan Software Engineer interview experience this question came from
Given a string `seq` containing only `A` and `B`, you may repeatedly delete either adjacent substring `AB` or adjacent substring `BB`.
After each deletion, concatenate the remaining prefix and suffix. Characters that were separated may become adjacent and form another deletable pair. Return the minimum possible length after any number of valid deletions, including zero deletions.
### Input and Output
- Input: the string `seq`.
- Output: one integer, the minimum remaining length over all valid deletion sequences.
### Constraints
- `1 <= len(seq) <= 200000`.
- Every character of `seq` is either `A` or `B`.
- A pair must be adjacent at the time it is deleted.
### Example
```text
seq = "BABBA"
answer = 1
```
Deleting the `AB` beginning at zero-based index `1` gives `BBA`. Deleting its leading `BB` then leaves `A`.
Constraints
- 1 <= len(seq) <= 200000.
- Every character of seq is A or B.
- Only an adjacent AB or BB may be deleted; the remaining pieces concatenate after deletion.
- Return the minimum possible length after zero or more deletions.
Examples
Input: ('BABBA',)
Expected Output: 1
Explanation: Deleting AB and then the newly adjacent BB leaves one A.
Input: ('AB',)
Expected Output: 0
Explanation: The only adjacent pair is deletable.
Hints
- A deletion always removes a pair whose right character is B.
- Concatenation can create a new adjacent pair.