2696. Minimum String Length After Removing Substrings

EasyView on LeetCode

String Stack Simulation

Time: O(n)

Space: O(n)

Intuition

Minimum string length after removing AB or CD substrings. Repeat until no more removals. Stack-based.

Algorithm

1Stack. For each char: if stack.top + char == AB or CD: pop. Else: push.
2Return stack size.

Common Pitfalls

•Stack handles nested removals automatically. Single pass O(n).

2696.cs

// Approach: Stack simulation; pop 'A' when 'B' arrives, pop 'C' when 'D' arrives.
// Time: O(n) Space: O(n)

public class Solution
{
    public int MinLength(string s)
    {
        Stack<char> st = new Stack<char>();
        foreach (char c in s)
        {
            if (c == 'B' && isMatched(st, 'A'))
                st.Pop();
            else if (c == 'D' && isMatched(st, 'C'))
                st.Pop();
            else
                st.Push(c);
        }

        return st.Count;
    }

    private bool isMatched(Stack<char> st, char c)
    {
        return st.Count > 0 && st.Peek() == c;
    }
}

Was this solution helpful?