# Minimum String Length After Removing Substrings
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-string-length-after-removing-substrings)
Canonical: https://scaleengineer.com/dsa/problems/minimum-string-length-after-removing-substrings
**Data structures:** String, Stack
**Companies:** [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Yelp](https://scaleengineer.com/companies/yelp)
---
## Problem
You are given a string `s` consisting only of **uppercase** English letters.

You can apply some operations to this string where, in one operation, you can remove **any** occurrence of one of the substrings `"AB"` or `"CD"` from `s`.

Return _the **minimum** possible length of the resulting string that you can obtain_.

**Note** that the string concatenates after removing the substring and could produce new `"AB"` or `"CD"` substrings.

**Example 1:**

**Input:** s = "ABFCACDB"
**Output:** 2
**Explanation:** We can do the following operations:
- Remove the substring "ABFCACDB", so s = "FCACDB".
- Remove the substring "FCACDB", so s = "FCAB".
- Remove the substring "FCAB", so s = "FC".
So the resulting length of the string is 2.
It can be shown that it is the minimum length that we can obtain.

**Example 2:**

**Input:** s = "ACBBD"
**Output:** 5
**Explanation:** We cannot do any operations on the string so the length remains the same.

**Constraints:**

* `1 <= s.length <= 100`
* `s` consists only of uppercase English letters.

# Approaches
## Iterative String Replacement
This approach simulates the removal process directly. It repeatedly scans the string to find and remove occurrences of `"AB"` or `"CD"` until no more such substrings can be found. This process continues until the string's length stabilizes.
**Time:** O(N^2), where N is the length of the string. The outer loop can run up to N/2 times, as we remove 2 characters in each successful iteration. Inside the loop, `indexOf` and `delete` on a `StringBuilder` can take up to O(N) time. Thus, the total time complexity is O(N * N) = O(N^2). · **Space:** O(N), where N is the length of the string. This is required to store the `StringBuilder`.
**Pros:** Conceptually simple and easy to implement.; Directly follows the logic of the problem description.
**Cons:** Inefficient due to repeated scanning of the string.; String/StringBuilder manipulation operations (`indexOf`, `delete`) inside a loop lead to quadratic time complexity, which can be slow for larger inputs.
### Explanation
The algorithm works by entering a loop that continues as long as removals are possible. In each iteration, it searches for the substrings `"AB"` or `"CD"`. If one is found, it's removed by modifying the string (or a `StringBuilder` for efficiency). The process is repeated on the new string. The loop terminates when a full pass over the string results in no removals. The length of the final string is the result.

For example, with `s = "ABFCACDB"`:
- 1. Find `"AB"` and remove it. `s` becomes `"FCACDB"`.
- 2. Find `"CD"` and remove it. `s` becomes `"FCAB"`.
- 3. Find `"AB"` and remove it. `s` becomes `"FC"`.
- 4. No more `"AB"` or `"CD"` can be found. The final length is 2.

```java
class Solution {
    public int minLength(String s) {
        StringBuilder sb = new StringBuilder(s);
        boolean found = true;
        while (found) {
            found = false;
            int abIndex = sb.indexOf("AB");
            if (abIndex != -1) {
                sb.delete(abIndex, abIndex + 2);
                found = true;
                // Restart search from the beginning as new pairs might have formed
                continue; 
            }
            
            int cdIndex = sb.indexOf("CD");
            if (cdIndex != -1) {
                sb.delete(cdIndex, cdIndex + 2);
                found = true;
            }
        }
        return sb.length();
    }
}
```
### Algorithm
- 1. Create a `StringBuilder` from the input string `s` for efficient modification.
- 2. Enter a loop that continues as long as the string can be shortened. A flag or checking the length before and after a pass can be used to control the loop.
- 3. Inside the loop, first search for an occurrence of the substring `"AB"`.
- 4. If `"AB"` is found, delete it from the `StringBuilder` and restart the search from the beginning of the modified string (e.g., by using `continue` in the loop).
- 5. If `"AB"` is not found, search for an occurrence of `"CD"`.
- 6. If `"CD"` is found, delete it and restart the search.
- 7. The loop terminates when a full pass is made without finding either `"AB"` or `"CD"`.
- 8. Return the length of the final `StringBuilder`.

## Optimal Approach using a Stack
A more efficient approach uses a stack to process the string in a single pass. As we iterate through the string, we use the stack to build the result. If the current character forms a removable pair (`"AB"` or `"CD"`) with the character at the top of the stack, we pop the stack. Otherwise, we push the current character onto the stack. This correctly handles all removals, including those that are formed by previous removals.
**Time:** O(N), where N is the length of the string. We iterate through the string once, and each stack operation (push, pop, peek) takes constant time on average. · **Space:** O(N) in the worst case. If no substrings can be removed (e.g., `s = "XYZ"`), the stack will store all N characters of the string.
**Pros:** Optimal time complexity of O(N).; Processes the string in a single pass.; Elegant solution for problems involving adjacent pair removals.
**Cons:** Requires O(N) extra space for the stack.; Slightly less intuitive than the direct simulation approach for beginners.
### Explanation
This method processes the string from left to right, character by character, maintaining a stack that represents the irreducible prefix of the string processed so far.

When we encounter a character, say `c`, we look at the top of the stack. If the stack is not empty and its top element forms a removable pair with `c` (e.g., top is 'A' and `c` is 'B'), it means we've found a substring like `"AB"`. We can effectively remove it by popping the 'A' from the stack and not pushing the 'B'. If no such pair is formed, we push `c` onto the stack.

After iterating through the entire input string, the number of characters remaining in the stack is the minimum possible length of the string.

Let's trace `s = "ABFCACDB"`:
- 1. `A`: push 'A'. Stack: `[A]`
- 2. `B`: top is 'A', forms `"AB"`. Pop. Stack: `[]`
- 3. `F`: push 'F'. Stack: `[F]`
- 4. `C`: push 'C'. Stack: `[F, C]`
- 5. `A`: push 'A'. Stack: `[F, C, A]`
- 6. `C`: push 'C'. Stack: `[F, C, A, C]`
- 7. `D`: top is 'C', forms `"CD"`. Pop. Stack: `[F, C, A]`
- 8. `B`: top is 'A', forms `"AB"`. Pop. Stack: `[F, C]`

The final stack size is 2.

```java
import java.util.Stack;

class Solution {
    public int minLength(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (!stack.isEmpty() && 
                ((stack.peek() == 'A' && c == 'B') || (stack.peek() == 'C' && c == 'D'))) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        return stack.size();
    }
}
```
An alternative implementation can use a `StringBuilder` as a stack for better performance, as `Stack` is a synchronized legacy class.
```java
class Solution {
    public int minLength(String s) {
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            int n = sb.length();
            if (n > 0 && 
                ((sb.charAt(n - 1) == 'A' && c == 'B') || (sb.charAt(n - 1) == 'C' && c == 'D'))) {
                sb.deleteCharAt(n - 1);
            } else {
                sb.append(c);
            }
        }
        return sb.length();
    }
}
```
### Algorithm
- 1. Initialize an empty stack of characters (a `java.util.Stack` or a `StringBuilder` acting as a stack can be used).
- 2. Iterate through each character `c` of the input string `s`.
- 3. For each character `c`, check if the stack is non-empty.
- 4. If it is, let `top` be the character at the top of the stack.
- 5. Check if `top` and `c` form a removable pair: `(top == 'A' and c == 'B')` or `(top == 'C' and c == 'D')`.
- 6. If they form a pair, pop the `top` element from the stack. This effectively removes the pair.
- 7. If they do not form a pair or if the stack was empty, push the current character `c` onto the stack.
- 8. After iterating through all characters, the size of the stack is the minimum length of the resulting string. Return this size.

# Solutions
### Java

```java
class Solution { public int minLength ( String s ) { Deque < Character > stk = new ArrayDeque <>(); stk . push ( ' ' ); for ( char c : s . toCharArray ()) { if (( c == 'B' && stk . peek () == 'A' ) || ( c == 'D' && stk . peek () == 'C' )) { stk . pop (); } else { stk . push ( c ); } } return stk . size () - 1 ; } }
```

### JavaScript

```javascript
function minLength ( s ) { const stk = []; for ( const c of s ) { if (( stk . at ( - 1 ) === ' A ' && c === ' B ' ) || ( stk . at ( - 1 ) === ' C ' && c === ' D ' )) { stk . pop (); } else { stk . push ( c ); } } return stk . length ; }
```

### CPP

```cpp
class Solution { public: int minLength ( string s ) { string stk = " " ; for ( char & c : s ) { if (( c == 'B' && stk . back () == 'A' ) || ( c == 'D' && stk . back () == 'C' )) { stk . pop_back (); } else { stk . push_back ( c ); } } return stk . size () - 1 ; } };
```

### Python

```python
class Solution : def minLength ( self , s : str ) -> int : stk = [ "" ] for c in s : if ( c == "B" and stk [ - 1 ] == "A" ) or ( c == "D" and stk [ - 1 ] == "C" ): stk . pop () else : stk . append ( c ) return len ( stk ) - 1
```