Question

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

Solution 1: Greedy + Stack

This problem is a classic parenthesis matching problem, which can be solved using "Greedy + Stack".

Iterate through each character $c$ in the string $s$:

• If $c$ is a left parenthesis, directly push $c$ into the stack;
• If $c$ is a right parenthesis, at this point if the stack is not empty, and the top element of the stack is a left parenthesis, then pop the top element of the stack, indicating a successful match; otherwise, push $c$ into the stack.

After the iteration ends, the number of remaining elements in the stack is the number of parentheses that need to be added.

The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the string $s$.

class Solution:
  def minAddToMakeValid(self, s: str) -> int:
    stk = []
    for c in s:
      if c == ')' and stk and stk[-1] == '(':
        stk.pop()
      else:
        stk.append(c)
    return len(stk)

class Solution {
  public int minAddToMakeValid(String s) {
    Deque<Character> stk = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
      if (c == ')' && !stk.isEmpty() && stk.peek() == '(') {
        stk.pop();
      } else {
        stk.push(c);
      }
    }
    return stk.size();
  }
}

class Solution {
public:
  int minAddToMakeValid(string s) {
    string stk;
    for (char c : s) {
      if (c == ')' && stk.size() && stk.back() == '(')
        stk.pop_back();
      else
        stk.push_back(c);
    }
    return stk.size();
  }
};

func minAddToMakeValid(s string) int {
  stk := []rune{}
  for _, c := range s {
    if c == ')' && len(stk) > 0 && stk[len(stk)-1] == '(' {
      stk = stk[:len(stk)-1]
    } else {
      stk = append(stk, c)
    }
  }
  return len(stk)
}

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

Solution 2: Greedy + Counting

Solution 1 uses a stack to implement parenthesis matching, but we can also directly implement it through counting.

Define a variable cnt to represent the current number of left parentheses to be matched, and a variable ans to record the answer. Initially, both variables are set to $0$.

Iterate through each character $c$ in the string $s$:

• If $c$ is a left parenthesis, increase the value of cnt by $1$;
• If $c$ is a right parenthesis, at this point if $cnt > 0$, it means that there are left parentheses that can be matched, so decrease the value of cnt by $1$; otherwise, it means that the current right parenthesis cannot be matched, so increase the value of ans by $1$.

After the iteration ends, add the value of cnt to ans, which is the answer.

The time complexity is $O(n)$, and the space complexity is $O(1)$, where $n$ is the length of the string $s$.

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

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

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