Problem : https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/
Instead of using stack, this is more like a greedy algorithm.
Scan the input string 2 times.
The 1st time scan, find the total number of valid left and right parentheses.
The 2nd time scan, greedily add the valid left and right parentheses.
Please be noticed, we cannot add right-parenthesis if there is no corresponding left-parenthesis be added before.
class Solution {
public String minRemoveToMakeValid(String s) {
char[] buffer = s.toCharArray();
// find total number valid parentheses
int unmatchedLeft = 0;
int validLeft = 0;
int validRight = 0;
for (char c : buffer) {
if (c == '(') {
unmatchedLeft += 1;
} else if (c == ')') {
if (unmatchedLeft > 0) {
unmatchedLeft -= 1;
validLeft += 1;
validRight += 1;
}
}
}
// greedily add valid parentheses
StringBuilder sb = new StringBuilder();
int left = 0;
int right = 0;
for (char c : buffer) {
if (c == '(' && left >= validLeft) {
continue;
}
// cannot add right-parenthesis
// if there is no corresponding left-parenthesis be added before
if (c == ')' && ( right >= validRight || left == right)) {
continue;
}
sb.append(c);
if (c == '(') {
left += 1;
} else if (c == ')') {
right += 1;
}
}
return sb.toString();
}
}