Teaching Kids Programming – Algorithms to Compute the Minimum String Length After Removing Substrings (Brute Force + Stack)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

Minimum String Length After Removing Substrings

We can solve this problem by using Brute Force Algorithm or using a Stack.

Brute Force Algorithm to Remove Substrings

As long as there is substring(s) “AB” or “CD”, we can remove it. Therefore, we can use the following straightforward solution. We use the string.replace function to remove a substring. Since string is immutable in Python, the string.replace will return a new copy of the string.

1
2
3
4
5

class Solution:
    def minLength(self, s: str) -> int:
        while "AB" in s or "CD" in s:
            s = s.replace("AB", "").replace("CD", "")
        return len(s)

class Solution:
    def minLength(self, s: str) -> int:
        while "AB" in s or "CD" in s:
            s = s.replace("AB", "").replace("CD", "")
        return len(s)

The time complexity is O(N^2). For example, if the string is “AAAAA…ABBBB…” then It takes O(N) time to find the substrings, and for each iteration, it costs O(N) time to remove the substring. Thus O(N^2).

The space complexity is O(N) as the string.replace requires an additional space usage.

Using a Stack to Remove Substrings

Instead of bruteforce, we can use a stack to keep tracking the characters. The Stack is First In Last Out, so if the top of the stack (previous character) concatenates the current character is one of the substrings (“AB”, “CD”), then we can safely/greedily pop from the stack, otherwise, we need to push the current character to the stack.

When all characters are visited, the remaining stack is the answer.

The time complexity is O(N), and the space complexity is O(N).

1
2
3
4
5
6
7
8
9

class Solution:
    def minLength(self, s: str) -> int:
        a = []
        for i in s:
            if a and a[-1] + i in ("AB", "CD"):
                a.pop()
            else:
                a.append(i)
        return len(a)

class Solution:
    def minLength(self, s: str) -> int:
        a = []
        for i in s:
            if a and a[-1] + i in ("AB", "CD"):
                a.pop()
            else:
                a.append(i)
        return len(a)

–EOF (The Ultimate Computing & Technology Blog) —