algoadvance

Leetcode 2696. Minimum String Length After Removing Substrings

Problem Statement

You are given a string s consisting of lowercase English letters. You need to repeatedly delete two adjacent characters in that string if they are either “AB” or “CD” and return the minimum possible length of the resulting string.

Clarifying Questions

Before we start solving the problem, it’s critical to clarify a few points:

  1. Can the string contain characters other than “A”, “B”, “C”, and “D”?
    • No, the string consists of lowercase English letters only, but knowing if there might be other characters helps in handling edge cases.
  2. Do we need to remove characters simultaneously or one pair at a time?
    • We need to remove pairs one at a time and continue to remove until no such pairs are present.
  3. Is there any constraint on the string length?
    • The constraints are provided by LeetCode. We will assume typical constraints and optimize our solution accordingly.
  4. How to handle empty strings?
    • If the string is empty, the minimum length is obviously 0.

Strategy

The problem can be approached using a stack. The stack-based approach works effectively here because it allows us to track characters and remove adjacent pairs efficiently.

  1. Traverse the string character by character.
  2. Push characters onto the stack.
  3. While pushing, check if the current character and the character at the top of the stack form either “AB” or “CD”. If so, pop the top character instead of pushing the current one.
  4. At the end of traversal, the stack will contain the resultant characters.

Code

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int minLengthAfterRemovingSubstrings(string s) {
    stack<char> stk;
    
    for (char ch : s) {
        if (!stk.empty() && (
            (stk.top() == 'A' && ch == 'B') ||
            (stk.top() == 'C' && ch == 'D'))) {
            stk.pop();
        } else {
            stk.push(ch);
        }
    }
    
    return stk.size();
}

int main() {
    string s;
    cin >> s;               // Input string can be taken from the user
    cout << minLengthAfterRemovingSubstrings(s) << endl;  // Displays the result
    return 0;
}

Time Complexity

The time complexity of the proposed solution is O(n), where n is the length of the string. This is because each character is processed exactly once, and stack operations (push and pop) are O(1).

The space complexity is also O(n) in the worst case where no pairs are removed, and all characters are stored in the stack.

Summary

This approach ensures that we can efficiently determine the minimum length of the string after repeatedly removing the substrings “AB” and “CD”. By leveraging a stack, we handle the adjacency and pairing conditions effectively, ensuring optimal time complexity.

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