• Posts

Problem 2696 Minimum String Length After Removing Substrings

Problem Statement

Link - Problem 2696

Question

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.

Solution

class Solution {
public:
    int minLength(string s) {
        stack<char> stack;

        for (int i = 0; i < s.length(); i++) {

            if (stack.empty()) {
                stack.push(s[i]);
                continue;
            }

            if (s[i] == 'B' && stack.top() == 'A') {
                stack.pop();
            }
            else if (s[i] == 'D' && stack.top() == 'C') {
                stack.pop();
            }
            else {
                stack.push(s[i]);
            }
        }

        return stack.size();
    }
};

Complexity Analysis

| Algorithm                    | Time Complexity | Space Complexity |
| ---------------------------- | --------------- | ---------------- |
| Stack-Based String Reduction | O(n)            | O(n)             |

Explanation

Intial Thoughts

To approach this problem, we should first think about how we can efficiently remove the given substrings. We can start by considering each character in the string and deciding whether to add it to our result or remove it if it matches the last character in our result. Another key point is to think about how we can store the characters we have seen so far in a way that allows us to easily check if the next character matches the last one in our result. We also need to consider the order in which we remove the substrings, as this can affect the final result. Additionally, we can think about using a data structure that allows us to efficiently add and remove characters. Lastly, we can look for a way to keep track of the minimum length of the resulting string.

Intuitive Analysis

One way to intuitively solve this problem is to imagine using a stack to store the characters we have seen so far. We can start by pushing the first character onto the stack, and then for each subsequent character, we check if it matches the top character on the stack. If it does, we pop the top character off the stack, effectively removing the substring. If it doesn’t, we push the new character onto the stack. We can continue this process until we have processed all characters in the string. Another key point is to think about how new substrings can be formed after removing a substring, and how we can efficiently handle this. We also need to consider the base case where no more substrings can be removed, and how we can use this to determine the minimum length of the resulting string. Furthermore, we can think about how to optimize our approach to minimize the number of operations. Finally, we can consider how to use the final state of the stack to determine the minimum length of the resulting string.

1. Intuition

• The problem can be approached by using a stack data structure to keep track of characters in the string s
• The key insight is to remove the substrings AB and CD from the string, which can be achieved by popping elements from the stack when these substrings are encountered
• The use of a stack allows for efficient removal of characters and handling of new substrings that may be formed after removal
• The algorithm iterates through the string s and checks for the presence of AB and CD substrings
• If a substring is found, the corresponding characters are removed from the stack, effectively reducing the length of the resulting string
• The final length of the resulting string is determined by the number of characters remaining in the stack
• This approach ensures that the minimum possible length of the resulting string is obtained

2. Implementation

• The solution uses a stack to store characters from the string s
• The for loop iterates through each character s[i] in the string s
• The if statement checks if the stack is empty, and if so, pushes the current character s[i] onto the stack
• The if-else statements check for the presence of AB and CD substrings by comparing the current character s[i] with the top element of the stack stack.top()
• If a substring is found, the top element is popped from the stack using stack.pop()
• Finally, the function returns the size of the stack stack.size(), which represents the minimum possible length of the resulting string
• The use of a stack allows for efficient implementation of the algorithm with a time complexity of O(n), where n is the length of the string s

Complexity Analysis

Time Complexity:

• The algorithm iterates over the string s once, resulting in a linear time complexity. Each iteration involves constant-time operations such as stack.push(s[i]) and stack.pop(), which do not affect the overall time complexity.
• The dominant operation is the for loop, which runs n times where n is the length of the string s. This leads to a time complexity of O(n), as the number of operations grows linearly with the size of the input.
• In all cases (worst, average, and best), the time complexity remains O(n) because the algorithm must examine each character in the string at least once to determine the minimum length.

Space Complexity:

• The algorithm uses a stack to keep track of the characters in the string, which requires additional memory. In the worst case, if no characters are popped from the stack, the space complexity will be O(n), where n is the length of the string s.
• The data structure used is a stack, which has a maximum size equal to the number of push operations. Since the algorithm pushes each character onto the stack at most once, the space complexity is directly related to the size of the input string.
• The space complexity remains O(n) in all cases because, even if some characters are popped from the stack, the maximum size of the stack is still proportional to the size of the input string.

Footnote

This question is rated as Easy difficulty.

Hints

Can we use brute force to solve the problem?

Repeatedly traverse the string to find and remove the substrings “AB” and “CD” until no more occurrences exist.

Can the solution be optimized using a stack?