Welcome to Subscribe On Youtube

921. Minimum Add to Make Parentheses Valid

Description

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 ')'.

Solutions

• Java
• C++
• Python
• Go
• TypeScript

• 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;
      }
  }
  

• 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;
      }
  };
  

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

• func minAddToMakeValid(s string) int {
  	ans, cnt := 0, 0
  	for _, c := range s {
  		if c == '(' {
  			cnt++
  		} else if cnt > 0 {
  			cnt--
  		} else {
  			ans++
  		}
  	}
  	ans += cnt
  	return ans
  }
  

• function minAddToMakeValid(s: string): number {
      const stk: string[] = [];
      for (const c of s) {
          if (c === ')' && stk.length > 0 && stk.at(-1)! === '(') {
              stk.pop();
          } else {
              stk.push(c);
          }
      }
      return stk.length;
  }
  
  

All Problems

All Solutions