LeetCode Entry
1249. Minimum Remove to Make Valid Parentheses
Remove minimum to make parenthesis valid
1249. Minimum Remove to Make Valid Parentheses medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/562
Problem TLDR
Remove minimum to make parenthesis valid #medium
Intuition
Let’s imagine some examples to better understand the problem:
(a
a(a
a(a()
(a))a
We can’t just append chars in a single pass. For example (a we don’t know if open bracket is valid or not.
The natural idea would be to use a Stack somehow, but it is unknown how to deal with letters then.
For this example: (a))a, we know that the second closing parenthesis is invalid, so the problem is straighforward. Now the trick is to reverse the problem for this case: (a -> a).
Approach
How many lines of code can you save?
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\)
Code
fun minRemoveToMakeValid(s: String) = buildString {
var open = 0
for (c in s) {
if (c == '(') open++
if (c == ')') open--
if (open >= 0) append(c)
open = max(0, open)
}
for (i in length - 1 downTo 0) if (get(i) == '(') {
if (--open < 0) break
deleteAt(i)
}
}
pub fn min_remove_to_make_valid(s: String) -> String {
let (mut open, mut res) = (0, vec![]);
for b in s.bytes() {
if b == b'(' { open += 1 }
if b == b')' { open -= 1 }
if open >= 0 { res.push(b) }
open = open.max(0)
}
for i in (0..res.len()).rev() {
if open == 0 { break }
if res[i] == b'(' {
res.remove(i);
open -= 1
}
}
String::from_utf8(res).unwrap()
}