Problem of The Day: Minimum String Length After Removing Substrings

3 min read 688 words

Problem Statement

leetcode problem link

Solution [accepted]

class Solution:
    def minLength(self, s: str) -> int:
        string = s[:]
        while True:
            new_string = string.replace('AB', '').replace('CD', '')
            if new_string == string:
                break
            string = new_string

        return len(string)

public class Solution {
    public int MinLength(string s) {
        while (true) {
            var new_s = s.Replace("AB","").Replace("CD","");
            if (new_s == s)
                break;
            s = new_s;
        }
        return s.Length;
    }
}

• time: O(n^2)
• space: O(n)

Editorial

Approach 1: String Replace

class Solution:
    def minLength(self, s: str) -> int:
        # Continue processing while "AB" or "CD" substrings exist
        while "AB" in s or "CD" in s:
            if "AB" in s:
                # Remove all occurrences of "AB"
                s = s.replace("AB", "")
            elif "CD" in s:
                # Remove all occurrences of "CD"
                s = s.replace("CD", "")

        return len(s)

Approach 2: Stack

class Solution:
    def minLength(self, s: str) -> int:
        stack = []

        # Iterate over each character in the input string
        for current_char in s:
            # If the stack is empty, simply push the current character
            if not stack:
                stack.append(current_char)
                continue

            # Check for "AB" pattern, remove the pair by popping from the stack
            if current_char == "B" and stack[-1] == "A":
                stack.pop()
            # Check for "CD" pattern, remove the pair by popping from the stack
            elif current_char == "D" and stack[-1] == "C":
                stack.pop()
            # Otherwise, push the current character onto the stack
            else:
                stack.append(current_char)

        return len(stack)

public class Solution {
    public int MinLength(string s) {
        Stack<char> stack = new Stack<char>();
        foreach (var c in s) {
            if (stack.Count == 0) {
                stack.Push(c);
                continue;
            }
            if (c == 'B' && stack.Peek() == 'A') {
                stack.Pop();
            } else if (c == 'D' && stack.Peek() == 'C') {
                stack.Pop();
            } else {
                stack.Push(c);
            }
        }
        return stack.Count;
    }
}