Skip to content

2696. Minimum String Length After Removing Substrings

Description

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.

Solutions

Solution 1: Stack

Thinking

AB and CD may be deleted and can cascade. Repeated replace is quadratic in the worst case. The rule matches parentheses: pop when the top and the current character form one of those pairs, otherwise push.

A dummy empty top avoids an empty-stack test; the leftover length minus one is the answer.

We traverse the string \(s\). For the current character \(c\) we are traversing, if the stack is not empty and the top element of the stack \(top\) can form \(AB\) or \(CD\) with \(c\), then we pop the top element of the stack, otherwise we push \(c\) into the stack.

The number of remaining elements in the stack is the length of the final string.

In implementation, we can pre-place an empty character in the stack, so there is no need to judge whether the stack is empty when traversing the string. Finally, we can return the size of the stack minus one.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the length of the string \(s\).

1
2
3
4
5
6
7
8
9
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func minLength(s string) int {
    stk := []byte{' '}
    for _, c := range s {
        if (c == 'B' && stk[len(stk)-1] == 'A') || (c == 'D' && stk[len(stk)-1] == 'C') {
            stk = stk[:len(stk)-1]
        } else {
            stk = append(stk, byte(c))
        }
    }
    return len(stk) - 1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function minLength(s: string): number {
    const stk: string[] = [];
    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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
impl Solution {
    pub fn min_length(s: String) -> i32 {
        let mut ans: Vec<u8> = Vec::new();

        for c in s.bytes() {
            if let Some(last) = ans.last() {
                if *last == b'A' && c == b'B' {
                    ans.pop();
                } else if *last == b'C' && c == b'D' {
                    ans.pop();
                } else {
                    ans.push(c);
                }
            } else {
                ans.push(c);
            }
        }

        ans.len() as i32
    }
}

Solution 2: One-liner

Thinking

Solution 1 uses an explicit stack. With length \(\le 100\), we may also strip AB|CD with a regular expression until the length stabilizes, written as a one-line recursion. Extra scans remain acceptable at this size.

1
2
const minLength = (s: string, n = s.length): number =>
    ((s = s.replace(/AB|CD/g, '')), s.length === n) ? n : minLength(s);

1
2
const minLength = (s, n = s.length) =>
    ((s = s.replace(/AB|CD/g, '')), s.length === n) ? n : minLength(s);

Comments