LeetCode Entry

2696. Minimum String Length After Removing Substrings

07.10.2024 easy 2024 kotlin rust

Remove 'AB' and 'CD' from the string

2696. Minimum String Length After Removing Substrings easy blog post substack youtube 1.webp

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: \(O(n)\)

  • Space complexity: \(O(n)\)

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();
    }