Skip to content

Instantly share code, notes, and snippets.

@laike9m
Created July 24, 2021 01:15
Show Gist options
  • Save laike9m/4fae68d8e6d85c673fa4b82a1e799cbd to your computer and use it in GitHub Desktop.
Save laike9m/4fae68d8e6d85c673fa4b82a1e799cbd to your computer and use it in GitHub Desktop.
1349
class Solution {
public:
bool isLetter(char c) {
return c >= 'a' && c <= 'z';
}
string minRemoveToMakeValid(string s) {
stack<pair<char, int>> sta;
string ans = "";
string buffer;
int left = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(') {
sta.push({'(', i});
} else if (s[i] == ')') {
if (!sta.empty() && sta.top().first == '(') {// the top of stack is '(', we find a valid pair.
sta.pop();
} else sta.push({')', i});
}
}
for (int i = s.length() - 1; i >= 0; i--) {
if (!sta.empty() && sta.top().second == i) {// we should remove this char
sta.pop();
continue;
}
ans = s[i] + ans;
}
return ans;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment