1249. Minimum Remove to Make Valid Parentheses
Use a stack.
Time = O(n)(three loops), space = O(n)(Stack, Set, StringBuilder)
class Solution {
public String minRemoveToMakeValid(String s) {
Deque<Integer> stack = new ArrayDeque<>();
List<Integer> indexesToRemove = new ArrayList<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
stack.offerFirst(i);
} else if (c == ')') {
if (!stack.isEmpty()) {
stack.pollFirst();
} else {
indexesToRemove.add(i);
}
}
}
while(!stack.isEmpty()) {
indexesToRemove.add(stack.pollFirst());
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (!indexesToRemove.contains(i)) {
sb.append(s.charAt(i));
}
}
return sb.toString();
}
}