LeetCode Entry

301. Remove Invalid Parentheses

07.10.2026 hard 2026 kotlin rust

Min removal to make balanced strings

301. Remove Invalid Parentheses hard substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1505

Problem TLDR

Min removal to make balanced strings

Intuition

DFS+backtrack: try to remove/keep every brace, update max at the end. BFS: each wave tries to remove every position from every string, stop at the first balanced string.

Approach

• dfs is easier to come up with by yourself

Complexity

• Time complexity: \(O(2^n)\)

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

Code

    fun removeInvalidParentheses(s: String): List<String> {
        fun valid(str: String) = str.scan(0) { b, c -> b + (c == '(').compareTo(c == ')') }
            .run { all { it >= 0 } && last() == 0 }
        return generateSequence(setOf(s)) { q ->
            q.flatMap { str -> str.indices.filter { str[it] in "()" }.map { str.removeRange(it..it) } }.toSet()
        }.first { q -> q.any(::valid) }.filter(::valid)
    }

    pub fn remove_invalid_parentheses(s: String) -> Vec<String> {
        let mut q = vec![s];
        loop {
            let (r, n): (Vec<_>,Vec<_>) = q.into_iter().partition(|s| 0 ==
                s.bytes().fold(0, |b,c| if b<0 {b} else {b+match c {40=>1,41=>-1,_=> 0}}));
            if r.len()>0 { return r }
            q = n.iter().flat_map(|s| (0..s.len()).filter(|&i| s.as_bytes()[i]/2==20).map(|i| s[..i].to_owned() + &s[i + 1..])).unique().collect()
        }
    }