algoadvance

Leetcode 2696. Minimum String Length After Removing Substrings

Problem Statement

Given a string s, you are tasked with removing instances of substrings “AB” and “CD” from the string as many times as possible until it’s not possible to remove any more substrings. Your final goal is to return the minimum possible length of the resulting string.

Clarifying Questions

• Q: Can the substrings “AB” and “CD” overlap during removal?
  • A: No, once “AB” or “CD” is removed, new adjacent substrings might be formed and should be considered in the next iteration.
• Q: What characters can the string s contain?
  • A: The string s will only consist of uppercase English letters.
• Q: Is there a maximum length for the string s?
  • A: Constraints are generally implied by the problem, but typical string length will be within reasonable bounds for typical coding challenges, e.g., up to 10^4 characters.

Strategy

1. Iterative Removal:
   • Continuously scan the string and remove all instances of “AB” and “CD”.
   • Use a stack to efficiently manage and check substrings around removed elements.
   • Continue removing until no more “AB” or “CD” is found in the string.
2. Stack Utilization:
   • Traverse the string using a stack.
   • Push characters onto the stack.
   • Whenever you see a character, check if the top of the stack and the current character form “AB” or “CD”. If they do, pop and discard them; otherwise, push the current character onto the stack.
   • By the end of the traversal, the remaining stack will represent the minimized string.

Code

Here is the solution to the problem:

public class Solution {
    public int minLength(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        
        for (char c : s.toCharArray()) {
            if (!stack.isEmpty() && ((stack.peek() == 'A' && c == 'B') || (stack.peek() == 'C' && c == 'D'))) {
                stack.pop(); // Remove the matching 'A' or 'C'
            } else {
                stack.push(c); // Push the current character onto the stack
            }
        }
        
        // The size of the stack is the minimum length of the string
        return stack.size();
    }
}

Time Complexity

• Time Complexity: O(n), where n is the length of the string. Each character is processed exactly once, either pushed onto the stack or then popped.
• Space Complexity: O(n) in the worst case, if no substrings “AB” or “CD” are found, the entire string is pushed onto the stack.

This approach ensures that we efficiently reduce the string length by treating removal of substrings through a stack structure, which provides a clean and simple O(n) solution.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?