You are given a string s composed of ‘(‘, ‘)’ and lowercase letters.
You need to remove the minimum number of ‘(‘ or ‘)’ (you can remove parentheses anywhere) from the string to make the rest of the ‘parenthesis string’ valid.
Please return any valid string.
A valid “parenthesis string” should meet any of the following requirements:
Empty strings or strings containing only lowercase letters can be written as strings AB (A concatenates B), where both A and B are valid “parenthesis strings” can be written as strings (A), where A is A valid “parenthesis string”
Their thinking
Example 1: s = “lee(t(c)o)de)” to see that the last) is redundant.
According to the stack idea, you can’t make a stack because the stack is empty.
So we can set a value CNT that simulates going on and going off, going on CNT ++, going off CNT — when CNT < 0, that proves that the current character is not a valid parenthesis and we can delete it.
You can only delete the redundant), so how to delete the redundant (
S = “(a(b(c)d)” (a(b(c)d)
We can iterate over the string in the opposite direction as we did above, and then delete the excess (
code
var minRemoveToMakeValid = function(s) { let ret = "", cnt = 0; for (k of s) { if (k == '(') { cnt++; ret += k; } else if (k == ')') { if (cnt == 0) continue cnt-- ret += k } else { ret += k } } s = ret.split('').reverse().join(''); ret = "", cnt = 0; for (k of s) { if (k == ')') { cnt++; ret += k; } else if (k == '(') { if (cnt == 0) continue cnt-- ret += k } else { ret += k } } return ret.split('').reverse().join(''); };Copy the code