Given a string s of (, ), and lowercase letters, remove the minimum number of invalid parentheses to make the string valid. Return the result.
Input: "lee(t(c)o)de)" → Output: "lee(t(c)o)de"Input: "a)b(c)d" → Output: "ab(c)d"
Use a stack to track indices of unmatched ( characters. Also track indices of unmatched ). Then remove all characters at those indices.
- Use a stack to store indices of unmatched (.
- Scan left to right: push index for (, for ) either pop from stack (match) or mark ) index for removal.
- After scan, all indices still in stack are unmatched ( — mark for removal.
- Build result skipping all marked indices.
import java.util.*;
class Solution {
public String minRemoveToMakeValid(String s) {
Set<Integer> remove = new HashSet<>();
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') stack.push(i);
else if (c == ')') {
if (!stack.isEmpty()) stack.pop();
else remove.add(i);
}
}
while (!stack.isEmpty()) remove.add(stack.pop());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++)
if (!remove.contains(i)) sb.append(s.charAt(i));
return sb.toString();
}
}
- Time Complexity: O(N)
- Space Complexity: O(N)