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.

 Example 1:

Input: s = "())"
Output: 1

Example 2:

Input: s = "((("
Output: 3

 Constraints:

• 1 <= s.length <= 1000
• s[i] is either '(' or ')'.

C++

• class Solution {
  public:
      int minAddToMakeValid(string s) {
          int ans = 0, cnt = 0;
          for (char c : s) {
              if (c == '(')
                  ++cnt;
              else if (cnt)
                  --cnt;
              else
                  ++ans;
          }
          ans += cnt;
          return ans;
      }
  };

JAVA

• class Solution {
      public int minAddToMakeValid(String s) {
          int ans = 0, cnt = 0;
          for (char c : s.toCharArray()) {
              if (c == '(') {
                  ++cnt;
              } else if (cnt > 0) {
                  --cnt;
              } else {
                  ++ans;
              }
          }
          ans += cnt;
          return ans;
      }
  }

PYTHON 

• class Solution:
      def minAddToMakeValid(self, s: str) -> int:
          ans = 0
          cnt = 0
          for c in s:
              if c == '(':
                  cnt += 1
              elif cnt > 0:
                  cnt -= 1
              else:
                  ans += 1
          ans += cnt
          return ans