Leetcode 1541. Minimum Insertions to Balance a Parentheses String

Problem Explanation

The problem requires you to check if a string of parentheses is balanced or not. A balanced parentheses string in this problem follows these two criteria:

1. Any left parenthesis '(' must have a corresponding two consecutive right parentheses '))'.
2. Left parenthesis '(' must go before the corresponding two consecutive right parentheses '))'.

You can insert parentheses at any position of the string to make it balanced, and your goal is to return the minimum number of insertions needed to make the string balanced.

For example:

• For string "(()))", it's almost balanced but missing a ')' to complete the first '('. We need to insert a ')' at the end making the string as "(())))" which is now balanced. So, the number of insertions required is 1.
• For string "())", it's already balanced. So, no insertion required and the result is 0.

Solution Approach

The approach is simple. We maintain three counters:

1. neededRight to indicate the number of ')' needed to form the pair with '('.
2. missingLeft to store number of '(' needed when we encounter ')' without '('.
3. missingRight to store number of ')' to make the pair for '(' if we encounter '))' quickly.

We loop through the string:

• When '(' is encountered, we check if neededRight is odd (after incrementing neededRight by 2 for each '('). If it is, it means we have encountered a '))' pair quicker than expected, so we increment missingRight and decrement neededRight.
• When ')' is encountered, we decrement neededRight. If neededRight is negative, it means a ')' is encountered without equivalent '('. So we increment missingLeft (meaning, we need one '(') and neededRight is increased by 2 (since we need to account for the other missing ')').

Finally, we return the sum of neededRight, missingLeft and missingRight as the minimum number of insertions required to make the string balanced.

Python Solution

1
2python
3class Solution:
4    def minInsertions(self, s: str) -> int:
5        neededRight = 0  
6        missingLeft = 0  
7        missingRight = 0
8
9        for c in s:
10            if c == '(':
11                if neededRight % 2 == 1:
12                    missingRight += 1
13                    neededRight -= 1
14                neededRight += 2
15            else:  # c == ')'
16                neededRight -= 1
17                if neededRight < 0:
18                    missingLeft += 1
19                    neededRight += 2
20
21        return neededRight + missingLeft + missingRight

Java Solution

1
2java
3class Solution {
4    public int minInsertions(String s) {
5        int neededRight = 0;
6        int missingLeft = 0;
7        int missingRight = 0;
8
9        for (char c : s.toCharArray()) {
10            if (c == '(') {
11                if (neededRight % 2 == 1) {
12                    missingRight++;
13                    neededRight--;
14                }
15                neededRight += 2;
16            } else {
17                neededRight--;
18                if (neededRight < 0) {
19                    missingLeft++;
20                    neededRight += 2;
21                }
22            }
23        }
24
25        return neededRight + missingLeft + missingRight;
26    }
27}

C# Solution

1
2csharp
3public class Solution {
4    public int MinInsertions(string s) {
5        int neededRight = 0;
6        int missingLeft = 0;
7        int missingRight = 0;
8
9        foreach (char c in s) {
10            if (c == '(') {
11                if (neededRight % 2 == 1) {
12                    missingRight++;
13                    neededRight--;
14                }
15                neededRight += 2;
16            } else {
17                neededRight--;
18                if (neededRight < 0) {
19                    missingLeft++;
20                    neededRight += 2;
21                }
22            }
23        }
24
25        return neededRight + missingLeft + missingRight;
26    }
27}

C++ Solution

1
2cpp
3class Solution {
4public:
5    int minInsertions(string s) {
6        int neededRight = 0, missingLeft = 0, missingRight = 0;
7
8        for (char c : s) {
9            if (c == '(') {
10                if (neededRight % 2 == 1) {
11                    missingRight++;
12                    neededRight--;
13                }
14                neededRight += 2;
15            } else {
16                neededRight--;
17                if (neededRight < 0) {
18                    missingLeft++;
19                    neededRight += 2;
20                }
21            }
22        }
23
24        return neededRight + missingLeft + missingRight;
25    }
26};

JavaScript Solution

1
2javascript
3class Solution {
4  minInsertions(s) {
5    let neededRight = 0;
6    let missingLeft = 0;
7    let missingRight = 0;
8
9    for (let i = 0; i < s.length; i++) {
10      let c = s.charAt(i);
11      if (c == '(') {
12        if (neededRight % 2 == 1) {
13          missingRight++;
14          neededRight--;
15        }
16        neededRight += 2;
17      } else {
18        neededRight--;
19        if (neededRight < 0) {
20          missingLeft++;
21          neededRight += 2;
22        }
23      }
24    }
25
26    return neededRight + missingLeft + missingRight;
27  }
28}

Ruby Solution

Similar to the previous solutions, in Ruby, we also check for each character of the string. If it is an open parenthesis, then we increment neededRight by 2 and check if we've encountered a )) pair earlier than expected. If it is a closing parenthesis, we decrement neededRight by 1 and check if we have encountered it without a corresponding open parenthesis.

The missingLeft, neededRight and missingRight variables keep track of different parenthesis requirements to balance the string.

1
2ruby
3class Solution
4    def minInsertions(s)
5        neededRight = 0
6        missingLeft = 0
7        missingRight = 0
8
9        s.chars.each do |c|
10            if c == '('
11                if neededRight % 2 == 1
12                    missingRight += 1
13                    neededRight -= 1
14                end
15                neededRight += 2
16            else
17                neededRight -= 1
18                if neededRight < 0
19                    missingLeft += 1
20                    neededRight += 2
21                end
22            end
23        end
24
25        return neededRight + missingLeft + missingRight
26    end
27end

The minInsertions(s) method returns the minimum number of insertions needed to make the string balanced.

Conclusion

Balancing parentheses in a string requires careful tracking of when the parentheses are expected to close and when there is a lack of opening or closing parentheses to pair them up. The number of required right, missing left, and missing right parentheses must be summed up to find the number of total insertions needed to balance the string fully.

The solution approach described here applies to several different programming languages, including Python, Java, JavaScript, Ruby, C#, and C++. It uses an algorithm that calculates the minimum number of insertions needed to balance the parentheses in the provided string, irrespective of the initial state of balance or imbalance.

The solutions demonstrated here can be readily used in real-world applications that need to process, validate, or interpret expressions, formulas, or text involving balanced parentheses.