1249. Minimum Remove to Make Valid Parentheses
Stack. Time = O(n), space = O(n)
class Solution {
public String minRemoveToMakeValid(String s) {
List<Integer> indexesToRemove = new ArrayList<>();
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.offerFirst(i);
} else if (s.charAt(i) == ')') {
if (stack.isEmpty()) {
indexesToRemove.add(i);
} else {
stack.pollFirst();
}
}
}
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();
}
}