Given a string with brackets, remove the fewest parentheses to make it valid. How do you count them, and how do you build the fixed string?
Predict first
What do the counter and the index-stack versions print?
func minRemovals(_ s: String) -> Int {
var open = 0, extraClose = 0
for c in s {
if c == "(" { open += 1 }
else if c == ")" { if open > 0 { open -= 1 } else { extraClose += 1 } }
}
return extraClose + open
}
func makeValid(_ s: String) -> String {
var chars = Array(s)
var stack: [Int] = []
for (i, c) in chars.enumerated() {
if c == "(" { stack.append(i) }
else if c == ")" { if stack.isEmpty { chars[i] = "\0" } else { stack.removeLast() } }
}
for i in stack { chars[i] = "\0" }
return String(chars.filter { $0 != "\0" })
}
for s in ["a)b(c)d", "))((", "lee(t(c)o)de)", "(a(b)c)"] {
print("\"\(s)\" -> remove \(minRemovals(s)) -> \"\(makeValid(s))\"")
}- "a)b(c)d" -> remove 1 -> "ab(c)d" / "))((" -> remove 4 -> "" / "lee(t(c)o)de)" -> remove 1 -> "lee(t(c)o)de" / "(a(b)c)" -> remove 0 -> "(a(b)c)"
- the same, but "))((" removes 2
- the same, but "a)b(c)d" removes 2
Mental model. Pairing socks: each right sock needs a left sock earlier in the pile. A right sock with no left sock before it is odd, and so is any left sock still waiting at the end.
Scan left to right keeping an open counter. An opening bracket increments it; a closing bracket with open > 0 pairs up and decrements; a closing bracket with open == 0 has no partner, so it must go (count it). At the end, whatever is still open never found a closer and must go too. The minimum number of removals is the unmatched closers plus the leftover openers: O(n) time, O(1) memory. For "))((" that is 4.
To return the fixed string, not just the count, keep a stack of the indices of the openers. A closer with an empty stack is marked for deletion; at the end every index still on the stack is marked too, and you rebuild the string from the unmarked characters. The check also keeps letters untouched ("a)b(c)d" becomes "ab(c)d"). Variations to name: several bracket types (use a stack of characters and a mapping), and “is this string valid?” (the same counter, return false when it would go negative or ends non-zero). Reported at Meta (anonymous, unverified).
Unmatched closers plus leftover openers are removed; letters stay and a balanced string is untouched.
Common traps
- Counting only total opens versus closes.
")("is balanced by count but invalid; order matters. - Removing characters while iterating, which shifts the indices; mark first, rebuild after.
They might follow up with
- Are all answers the same string? No: removing a different but equally short set can give another valid string; ask whether any one is fine.
- How do you check validity with three bracket types? A stack of expected closers; mismatch or leftover means invalid.
Related questions
- 29.1.4 Add two non-negative numbers given as decimal strings, without converting them to integers. Why can you not…
- 29.1.6 Can a string be built by concatenating words from a list (words may repeat)? How do you answer yes or no, and…
- 29.1.8 When do you use a sliding window, and how do the fixed-size and variable-size versions differ?
← Add two non-negative numbers given as decimal strings, without… Can a string be built by concatenating words from a list (words may… →