2696. Minimum String Length After Removing Substrings LeetCode Solution

In this guide, you will get 2696. Minimum String Length After Removing Substrings LeetCode Solution with the best time and space complexity. The solution to Minimum String Length After Removing Substrings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Minimum String Length After Removing Substrings solution in C++
4. Minimum String Length After Removing Substrings solution in Java
5. Minimum String Length After Removing Substrings solution in Python
6. Additional Resources

Problem Statement of Minimum String Length After Removing Substrings

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.

Complexity Analysis

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

2696. Minimum String Length After Removing Substrings LeetCode Solution in C++

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

    for (const char c : s)
      if (c == 'B' && match(stack, 'A'))
        stack.pop();
      else if (c == 'D' && match(stack, 'C'))
        stack.pop();
      else
        stack.push(c);

    return stack.size();
  }

 private:
  bool match(const stack<char>& stack, int c) {
    return !stack.empty() && stack.top() == c;
  }
};
/* code provided by PROGIEZ */

2696. Minimum String Length After Removing Substrings LeetCode Solution in Java

class Solution {
  public int minLength(String s) {
    Deque<Character> stack = new ArrayDeque<>();

    for (final char c : s.toCharArray())
      if (c == 'B' && match(stack, 'A'))
        stack.pop();
      else if (c == 'D' && match(stack, 'C'))
        stack.pop();
      else
        stack.push(c);

    return stack.size();
  }

  private boolean match(Deque<Character> stack, char c) {
    return !stack.isEmpty() && stack.peek() == c;
  }
}
// code provided by PROGIEZ

2696. Minimum String Length After Removing Substrings LeetCode Solution in Python

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

    def match(c: str) -> bool:
      return stack and stack[-1] == c

    for c in s:
      if c == 'B' and match('A'):
        stack.pop()
      elif c == 'D' and match('C'):
        stack.pop()
      else:
        stack.append(c)

    return len(stack)
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.