LeetCode: Minimum Add to Make Parentheses Valid Solution

Approach: Maintain balance

If it is an open ( then we need a close, so needClose++

If it is a close )

• if close are in need, satisfy it, needClose--
• if there is no close in need at the moment, then we need a open, needOpen++

The result is the sum of both in need

Implementation

1var minAddToMakeValid = function (s) {
2  let needOpen = 0
3  let needClose = 0
4
5  for (const char of s) {
6    if (char === "(") {
7      needClose++
8    }
9
10    if (char === ")") {
11      if (needClose > 0) {
12        needClose--
13      } else {
14        needOpen++
15      }
16    }
17  }
18
19  return needOpen + needClose
20}

Approach: Stack

Keep adding to stack

Popout () pairs during the process

The amount of what are need is the stack leftover

Implementation

1var minAddToMakeValid = function (s) {
2  const stack = []
3
4  for (const char of s) {
5    if (char === "(") {
6      stack.push(char)
7    }
8
9    if (char === ")") {
10      if (stack.slice(-1)[0] === "(") {
11        stack.pop()
12      } else {
13        stack.push(char)
14      }
15    }
16  }
17
18  return stack.length
19}

References

Original problem

Similar problems

Minimum Number of Swaps to Make the String Balanced