LeetCode: Minimum Add to Make Parentheses Valid Solution

Maintain balance, and yes, also naming variables

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

Comments

Loading comments...

Tags

leetcode

string

greedy

stack

Next Post

LeetCode: Minimum ASCII Delete Sum for Two Strings

Oct 31, 2022

Modified version of Longest Common Subsequence problem

Previous Post

LeetCode: Combination Sum II

Oct 24, 2022

Backtracking with duplication check

HoningJS

Search Posts