1541. Minimum Insertions to Balance a Parentheses String LeetCode Solution

In this guide, you will get 1541. Minimum Insertions to Balance a Parentheses String LeetCode Solution with the best time and space complexity. The solution to Minimum Insertions to Balance a Parentheses String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Minimum Insertions to Balance a Parentheses String solution in C++
  4. Minimum Insertions to Balance a Parentheses String solution in Java
  5. Minimum Insertions to Balance a Parentheses String solution in Python
  6. Additional Resources
1541. Minimum Insertions to Balance a Parentheses String LeetCode Solution image

Problem Statement of Minimum Insertions to Balance a Parentheses String

Given a parentheses string s containing only the characters ‘(‘ and ‘)’. A parentheses string is balanced if:

Any left parenthesis ‘(‘ must have a corresponding two consecutive right parenthesis ‘))’.
Left parenthesis ‘(‘ must go before the corresponding two consecutive right parenthesis ‘))’.

In other words, we treat ‘(‘ as an opening parenthesis and ‘))’ as a closing parenthesis.

For example, “())”, “())(())))” and “(())())))” are balanced, “)()”, “()))” and “(()))” are not balanced.

You can insert the characters ‘(‘ and ‘)’ at any position of the string to balance it if needed.
Return the minimum number of insertions needed to make s balanced.

Example 1:

Input: s = “(()))”
Output: 1
Explanation: The second ‘(‘ has two matching ‘))’, but the first ‘(‘ has only ‘)’ matching. We need to add one more ‘)’ at the end of the string to be “(())))” which is balanced.

See also  2415. Reverse Odd Levels of Binary Tree LeetCode Solution

Example 2:

Input: s = “())”
Output: 0
Explanation: The string is already balanced.

Example 3:

Input: s = “))())(”
Output: 3
Explanation: Add ‘(‘ to match the first ‘))’, Add ‘))’ to match the last ‘(‘.

Constraints:

1 <= s.length <= 105
s consists of '(' and ')' only.

Complexity Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(1)

1541. Minimum Insertions to Balance a Parentheses String LeetCode Solution in C++

class Solution {
 public:
  int minInsertions(string s) {
    int neededRight = 0;   // Increment by 2 for each '('.
    int missingLeft = 0;   // Increment by 1 for each missing '('.
    int missingRight = 0;  // Increment by 1 for each missing ')'.

    for (const char c : s)
      if (c == '(') {
        if (neededRight % 2 == 1) {
          // e.g. "()(..."
          ++missingRight;
          --neededRight;
        }
        neededRight += 2;
      } else if (--neededRight < 0) {  // c == ')'
        // e.g. "()))..."
        ++missingLeft;
        neededRight += 2;
      }

    return neededRight + missingLeft + missingRight;
  }
};
/* code provided by PROGIEZ */

1541. Minimum Insertions to Balance a Parentheses String LeetCode Solution in Java

class Solution {
  public int minInsertions(String s) {
    int neededRight = 0;  // Increment by 2 for each '('.
    int missingLeft = 0;  // Increment by 1 for each missing '('.
    int missingRight = 0; // Increment by 1 for each missing ')'.

    for (final char c : s.toCharArray())
      if (c == '(') {
        if (neededRight % 2 == 1) {
          // e.g. "()(..."
          ++missingRight;
          --neededRight;
        }
        neededRight += 2;
      } else if (--neededRight < 0) { // c == ')'
        // e.g. "()))..."
        ++missingLeft;
        neededRight += 2;
      }

    return neededRight + missingLeft + missingRight;
  }
}
// code provided by PROGIEZ

1541. Minimum Insertions to Balance a Parentheses String LeetCode Solution in Python

class Solution:
  def minInsertions(self, s: str) -> int:
    neededRight = 0   # Increment by 2 for each '('.
    missingLeft = 0   # Increment by 1 for each missing '('.
    missingRight = 0  # Increment by 1 for each missing ')'.

    for c in s:
      if c == '(':
        if neededRight % 2 == 1:
          # e.g. '()(...'
          missingRight += 1
          neededRight -= 1
        neededRight += 2
      else:  # c == ')'
        neededRight -= 1
        if neededRight < 0:
          # e.g. '()))...'
          missingLeft += 1
          neededRight += 2

    return neededRight + missingLeft + missingRight
# code by PROGIEZ

Additional Resources

See also  1498. Number of Subsequences That Satisfy the Given Sum Condition LeetCode Solution

Happy Coding! Keep following PROGIEZ for more updates and solutions.