# 07.10.2024 [2696. Minimum String Length After Removing Substrings]

Remove 'AB' and 'CD' from the string #easy #stack

07.10.2024

2696. Minimum String Length After Removing Substrings easy
blog post

youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/759

Problem TLDR

Remove ‘AB’ and ‘CD’ from the string #easy #stack

Intuition

We can do the removals in a loop until the string size changes.
However, the optimal way is to do this with a Stack: pop if stack top and the current char form the target to remove.

Approach

• Rust has a nice match to shorten the code

Complexity

• Time complexity:
  𝑂(𝑛)

• Space complexity:
  𝑂(𝑛)

Code

    fun minLength(s: String)= Stack<Char>().run {
        for (c in s) if (size > 0 && 
            (c == 'B' && peek() == 'A' || c == 'D' && peek() == 'C')) 
            pop() else push(c)
        size
    }

    pub fn min_length(s: String) -> i32 {
        let mut stack = vec![];
        for b in s.bytes() { match b {
            b'B' if stack.last() == Some(&b'A') => { stack.pop(); }
            b'D' if stack.last() == Some(&b'C') => { stack.pop(); }
            _ => { stack.push(b) }
        }}
        stack.len() as i32
    }

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