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
• Java 2
• C++ 2
• Python 2
• Go 2
• TypeScript 2
• TypeScript 3
• Javascript 3

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

• 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 {
      let [ans, cnt] = [0, 0];
      for (const c of s) {
          if (c === '(') {
              ++cnt;
          } else if (cnt) {
              --cnt;
          } else {
              ++ans;
          }
      }
      ans += cnt;
      return ans;
  }
  
  

• function minAddToMakeValid(s: string): number {
      const l = s.length;
      s = s.replace('()', '');
  
      return s.length === l ? l : minAddToMakeValid(s);
  }
  
  

• /**
   * @param {string} s
   * @return {number}
   */
  var minAddToMakeValid = function (s) {
      const l = s.length;
      s = s.replace('()', '');
      return s.length === l ? l : minAddToMakeValid(s);
  };
  
  

All Problems

All Solutions