[LeetCode] Minimum Add to Make Parentheses Valid

921. Minimum Add to Make Parentheses Valid

A parentheses string is valid if and only if:

  • It is the empty string,
  • It can be written as AB (A concatenated with B), where A and B are valid strings, or
  • It can be written as (A), where A is a valid string.

You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.

  • For example, if s = “()))”, you can insert an opening parenthesis to be “(()))” or a closing parenthesis to be “())))”.

Return the minimum number of moves required to make s valid.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int minAddToMakeValid(string s) {
vector<char> st;
for(auto& c : s) {
if(st.empty() || c == '(') st.push_back(c);
else if(st.back() == '(') st.pop_back();
else st.push_back(c);
}

return st.size();
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2021/12/13/PS/LeetCode/minimum-add-to-make-parentheses-valid/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.