The problem. Given a string s of lowercase letters, ( and ), remove the fewest parentheses so that the rest is valid — every ) closes an earlier ( and every ( is closed. Return any valid result.
s = "lee(t(c)o)de)" -> "lee(t(c)o)de"
s = "a)b(c)d(" -> "ab(c)d"
s = "))((" -> ""Some brackets can never be part of a valid string: a ) with no open ( before it, and a ( that is still open when the string ends. Every other bracket can stay. Removing exactly the unmatchable ones is therefore the minimum — and finding them is the stack's job, since a ) always closes the most recent open (.
Because positions matter (we must know which ( to delete at the end), the stack holds indexes, not characters.
A counter is enough if you scan twice. Left to right, drop each ) that arrives when nothing is open. Then whatever is still open are extra ( — scanning right to left, drop that many ( from the end.
function minRemoveToMakeValid(s) { // Pass 1, left to right: drop every ')' with no '(' before it. const kept = []; let balance = 0; for (const ch of s) { if (ch === "(") balance++; else if (ch === ")") { if (balance === 0) continue; balance--; } kept.push(ch); } // Pass 2, right to left: drop the last 'balance' unmatched '('. const out = []; for (let i = kept.length - 1; i >= 0; i--) { if (kept[i] === "(" && balance > 0) { balance--; continue; } out.push(kept[i]); } return out.reverse().join("");}Time O(n), space O(n). Two linear passes and two builders. Dropping the last extra ( is always safe: none of them has a ) after it waiting to be matched.
Push the index of every (. A ) pops the most recent one — a match — or, if the stack is empty, is marked for removal. Whatever indexes remain on the stack at the end are unclosed (: mark those too, then build the string without the marked positions.
The stack holds indexes of open '('; unmatched ')' and leftover '(' are greyed out and removed.
function minRemoveToMakeValid(s) { const chars = [...s]; const open = []; // indexes of '(' still waiting for a match for (let i = 0; i < chars.length; i++) { if (chars[i] === "(") open.push(i); else if (chars[i] === ")") { if (open.length > 0) open.pop(); // matches the most recent '(' else chars[i] = ""; // nothing to match: remove it } } for (const i of open) chars[i] = ""; // '(' never matched: remove them too return chars.join("");}Time O(n), space O(n). One scan, a final pass over the leftover indexes, and one pass to build the answer.
Both are linear. The stack version names the unmatched brackets exactly, which makes it easy to explain why the removal is minimal; the counter version shows you only needed a count, not the whole stack, as long as you scan twice.
"))((": everything goes."())" can keep either ); any valid answer of maximum length is accepted, so test by checking validity and length, not one fixed string.) plus ( left open.