2696. Minimum String Length After Removing Substrings

EasyStackStringSimulation
Leetcode Link

Problem Description

In this problem, we are provided with a string s which contains only uppercase English letters. We are allowed to perform operations on this string, where one operation consists of removing any occurrence of the substrings "AB" or "CD" from s.

The goal is to determine the minimum possible length of the string s after applying any number of operations. An operation may create the opportunity to perform additional operations, as the removal of a substring could cause new occurrences of "AB" or "CD" to form by concatenation of the characters before and after the removed substring.

To note, it is not necessary that we remove all possible occurrences of "AB" or "CD" in one go. As we remove substrings, we need to keep checking if new occurrences appear, and remove those as well until no more removals are possible.

Intuition

The intuition behind the solution is to simulate the process of removing substrings iteratively in an efficient manner. A naïve approach might involve repeatedly scanning the string and removing occurrences of the target substrings which can be very inefficient.

A more efficient method is to use a stack data structure to keep track of the characters in the string as we iterate over it. We push each character onto the stack, but before we do that, we check the character on top of the stack. If the current character along with the character at the top of the stack forms a forbidden substring ("AB" or "CD"), we pop the top character from the stack instead of pushing the current character. This effectively removes the forbidden substring from the string.

By using a stack, we are processing each character only once, which makes this a linear time operation (O(n), where n is the length of the string s). The stack helps us to keep track of the characters that have potential to form a forbidden substring with future characters. At the end of the iteration, the characters left in the stack represent the final string after all possible removals of "AB" and "CD" substrings.

The length of the final string is the number of elements in the stack, minus one to account for the dummy element at the bottom of the stack that was used as an initial placeholder.

Learn more about Stack patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Solution Approach

To implement the solution, we use a simple yet powerful data structure: the stack. A stack is a collection of elements with two main operations — push (add an element to the top) and pop (remove the top element).

Here's a step-by-step explanation of how the code uses a stack to solve the problem:

  1. We initialize an empty stack with a dummy character at the bottom: stk = [""].
  2. We then iterate over each character c in the input string s.
  3. On encountering each character, we check the top element of the stack:
    • If the current character c is "B" and the last character in the stack is "A" (which means we found "AB"), we pop the last character from the stack.
    • If the current character c is "D" and the last character in the stack is "C" (which means we found "CD"), we pop the last character from the stack.
    • These conditions check for the presence of the forbidden substrings, stk[-1] refers to the top element of the stack.
  4. If neither of the above conditions are met, it means the current character doesn’t form a forbidden substring with the character at the top of the stack. So we push the current character onto the stack.
  5. After the loop ends, the characters left in the stack represent the characters of the string after all the operations been applied. The stack does not include possible forbidden substrings formed by adjacent characters.
  6. The length of the resultant string, which is also the minimum length possible after operations, is the size of the stack minus one (to account for the initial dummy character).
  7. Finally, we return len(stk) - 1.

This implementation takes advantage of the stack pattern's Last-In-First-Out (LIFO) property to efficiently track and remove substrings that match the criteria as we traverse the string. The time complexity of this implementation is O(n), where n is the length of the string s, since we go through each character exactly once.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

In a binary min heap, the minimum element can be found in:

Example Walkthrough

Let's consider an example to illustrate the solution approach with the input string s = "ACBDACBD".

Here's how the algorithm progresses:

  1. Initialize the stack: Start with an empty stack with a dummy character. stk = [""].
  2. Process first character "A": Since "A" doesn’t form "AB" or "CD" with the dummy character, we push "A" onto the stack. stk = ["", "A"].
  3. Process second character "C": "C" also doesn’t complete any forbidden substring, so we push it. stk = ["", "A", "C"].
  4. Process third character "B": Now, "B" with the preceding "C" does not form a forbidden substring. Therefore, push "B". stk = ["", "A", "C", "B"].
  5. Process fourth character "D": "D" after "B" does not form a forbidden substring either, so we push "D". stk = ["", "A", "C", "B", "D"].
  6. Process fifth character "A": No forbidden substring with "D", so "A" is pushed. stk = ["", "A", "C", "B", "D", "A"].
  7. Process sixth character "C": As "C" follows "A", nothing is removed, and we push "C". stk = ["", "A", "C", "B", "D", "A", "C"].
  8. Process seventh character "B": "B" is coming after "C", which does form the forbidden substring "CB" (Note: Only "AB" and "CD" are forbidden, not "CB".). Push "B". stk = ["", "A", "C", "B", "D", "A", "C", "B"].
  9. Process eighth character "D": Finally, we encounter "D" after "B". The "CD" forms a forbidden substring, so rather than pushing "D", we pop "C" from the stack. Now, the stack is stk = ["", "A", "C", "B", "D", "A", "B"].

After iterating through the entire string, we are left with the stack containing the elements from our original string minus any "AB" or "CD" substrings. The length of our final reduced string is len(stk) - 1 = 6.

Therefore, the minimum possible length of the string s after applying the operations is 6.

Solution Implementation

1class Solution:
2    def minLength(self, s: str) -> int:
3        # Initialize a stack with an empty string to simplify edge cases
4        # such as when the input string is empty or when we need to check 
5        # the top element without additional null checks.
6        stack = [""]
7      
8        # Iterate through each character 'c' in the input string 's'
9        for c in s:
10            # If the condition is met for removing characters, i.e.,
11            # - if current character is 'B' and the top of the stack is 'A', or
12            # - if current character is 'D' and the top of the stack is 'C',
13            # then pop the top element from the stack as the pair is valid
14            # for removal, according to the problem's conditions.
15            if (c == "B" and stack[-1] == "A") or (c == "D" and stack[-1] == "C"):
16                stack.pop()
17            else:
18                # If the current character does not meet the conditions
19                # for removal, then add ('push') this character onto the stack.
20                stack.append(c)
21      
22        # After processing all characters, the stack will contain the characters
23        # that cannot be removed by the rules of the problem. Since we started
24        # with an empty string in the stack, we subtract 1 to get the actual
25        # number of characters in the final string.
26        return len(stack) - 1
27
28# The class method 'minLength' can be used by creating an instance of the Solution class
29# and calling 'minLength' with a specific string. For example:
30# solution = Solution()
31# result = solution.minLength("ACBDAC")
32# print(result) will print the length of the string after removal operations.
33
1class Solution {
2    // Method to determine the minimum length of the string 
3    // after performing the given reduction operations.
4    public int minLength(String s) {
5        // Initialize a stack to hold characters.
6        Deque<Character> stack = new ArrayDeque<>();
7        // Add a space as a sentinel to the stack to avoid empty stack checks.
8        stack.push(' ');
9
10        // Iterate over each character in the string.
11        for (char currentChar : s.toCharArray()) {
12            // Check for the conditions to pop the top of the stack.
13            // If the current character is 'B' and the top is 'A', or
14            // if the current character is 'D' and the top is 'C', then pop.
15            if ((currentChar == 'B' && stack.peek() == 'A') || (currentChar == 'D' && stack.peek() == 'C')) {
16                stack.pop();
17            } else {
18                // Push the current character onto the stack if no pair is found.
19                stack.push(currentChar);
20            }
21        }
22        // Return the stack size minus one to exclude the initial sentinel space.
23        return stack.size() - 1;
24    }
25}
26
1class Solution {
2public:
3    // Method to calculate the minimum length of the string after performing reductions.
4    int minLength(string s) {
5        // Initialize a stack represented by a string with an extra space to handle empty stack case.
6        string stack = " ";
7      
8        // Iterate over each character in the input string.
9        for (char& c : s) {
10            // Check for reduction conditions: 'B' with 'A', or 'D' with 'C'.
11            // If the condition is satisfied, pop the last character from the 'stack'.
12            if ((c == 'B' && stack.back() == 'A') || (c == 'D' && stack.back() == 'C')) {
13                stack.pop_back();
14            } else {
15                // If no reduction is possible, push the current character onto the 'stack'.
16                stack.push_back(c);
17            }
18        }
19      
20        // Return the size of the stack minus one for the extra space at the beginning.
21        // This gives the minimum length of the string after performing reductions.
22        return stack.size() - 1;
23    }
24};
25
1/**
2 * Calculates the minimum length of a string after removing specific pairs.
3 * Pairs 'AB' and 'CD' are removed when encountered in the string.
4 * @param {string} inputString - The original string.
5 * @return {number} - The minimum length of the string after removals.
6 */
7function minLength(inputString: string): number {
8    // Initialize a stack with an empty string to simplify checks
9    const stack: string[] = [''];
10
11    // Loop through each character in the input string
12    for (const character of inputString) {
13        // Peek at the last element of the stack
14        const lastElement = stack[stack.length - 1];
15      
16        // Check for and handle 'AB' pair
17        if (character === 'B' && lastElement === 'A') {
18            stack.pop();
19        }
20        // Check for and handle 'CD' pair
21        else if (character === 'D' && lastElement === 'C') {
22            stack.pop();
23        }
24        // If no pairs are found, push the current character to the stack
25        else {
26            stack.push(character);
27        }
28    }
29
30    // Subtract one since we added an empty string at the start
31    return stack.length - 1;
32}
33
Not Sure What to Study? Take the 2-min Quiz：

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Time and Space Complexity

The given code snippet defines a function minLength which processes a string s by simulating a stack to remove certain pairs of adjacent characters ('B' with a preceding 'A', and 'D' with a preceding 'C'). The algorithm uses a stack stk with a sentinel value (an empty string) pre-loaded, thus avoiding empty stack checks during the iteration.

Time Complexity:

The time complexity of this function is O(n) where n is the length of the input string s. This is because the function goes through each character in the string exactly once. At each character, it performs a constant-time check (c == "B" with stk[-1] == "A" or c == "D" with stk[-1] == "C") and either pushes the character to the stack or pops from the stack. Both operations, pushing to and popping from the end of a list (which is used to simulate the stack in Python), occur in O(1) time. Thus, the overall time taken is proportional to the length of the string.

Space Complexity:

The space complexity of the algorithm can also be considered as O(n). This is because in the worst-case scenario, none of the characters can be popped off the stack, and the stack would grow to contain all n characters from the input string. This would happen when there are no qualifying pairs ('B' with 'A' or 'D' with 'C') in the entire string. The sentinel value in the stack does not affect the complexity as it is a constant space overhead.

In summary:

  • Time Complexity: O(n)
  • Space Complexity: O(n)

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫