Find the Shortest Length After Removing AB and CD
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Other
# Find the Shortest Length After Removing AB and CD
You are given a string `s` containing only uppercase English letters. In one operation, remove any occurrence of the contiguous substring `AB` or `CD`.
The pieces on either side concatenate after a removal, so an operation can create a new removable substring. Choose the operations and their order to minimize the final length, and return that length.
### Examples
**Example 1**
```text
Input: s = "ACDBCD"
Output: 0
```
Remove the first `CD` to obtain `ABCD`, remove `AB` to obtain `CD`, then remove that last pair. The resulting string is empty.
**Example 2**
```text
Input: s = "BACDABZ"
Output: 3
```
Removing `CD` gives `BAABZ`. Removing its `AB` gives `BAZ`, with length `3`. The reverse pair `BA` is not removable.
### Constraints
- `1 <= s.size() <= 100`.
- Every character of `s` is an uppercase English letter.
### Clarifying Questions
- Can letters separated by other characters be removed together? Only if earlier operations make them adjacent; each removal must use a current substring.
- Are `BA` or `DC` also removable? No; only `AB` and `CD` qualify.
- Can the answer be zero despite the nonempty input? Yes; the resulting string may be empty.
- Is the remaining string required? No; return only its minimum possible length.
### C++ Interface
```cpp
class Solution {
public:
int minLength(string s) {
}
};
```
### Reasoning Checkpoints
- Account for new adjacency after each removal.
- Distinguish contiguous substrings from subsequences.
- Justify that the chosen removal order attains a minimum.
```hint Newly adjacent letters
After deleting a pair, where can the next newly created removable pair appear?
```
Overview: Remove occurrences of AB or CD from an uppercase string, allowing newly joined letters to form further removable pairs. Return the minimum reachable length, including an empty result, and distinguish the allowed pairs from their reversals.