Practice/Meta/Leetcode 1541. Minimum Insertions to Balance a Parentheses String

Leetcode 1541. Minimum Insertions to Balance a Parentheses String

CodingMust

Problem

You are given a string containing only the characters '(' and ')'. However, in this problem, the parentheses follow a special balancing rule: each opening bracket '(' must be closed by exactly two consecutive closing brackets '))'.

Your task is to find the minimum number of bracket insertions (either '(' or ')') needed at any position in the string to make it balanced according to this rule.

A balanced string under this rule means:

• Every '(' has exactly two ')' following it (not necessarily immediately)
• Every pair of '))' has a matching '(' before it
• All brackets are properly paired with no unmatched characters

Requirements

1. Return the minimum number of character insertions needed
2. Insertions can be made at any position in the string
3. Only '(' and ')' characters are present in the input
4. Handle both missing opening brackets and missing closing brackets
5. Remember that each opening bracket requires TWO closing brackets

Constraints

• 1 ≤ s.length ≤ 100,000
• s consists only of '(' and ')'
• Time complexity should be O(n)
• Space complexity should be O(1)

Examples

Example 1:

` Input: s = "(()))" Output: 1 Explanation:

• First '(' matches with '))'
• Second '(' matches with ')' but needs one more ')'
• Total insertions needed: 1 `

Example 2:

` Input: s = "())" Output: 1 Explanation:

• The '(' matches with the first ')'
• The second ')' is alone and needs a '(' before it
• Total insertions needed: 1 (insert '(' at beginning) `

Example 3:

` Input: s = "))())(" Output: 3 Explanation:

• First ')' needs a '(' (1 insertion)
• The pattern continues with missing opens and closes
• Total insertions needed: 3 `

Example 4:

` Input: s = "(((" Output: 6 Explanation:

• Each '(' needs '))' to close it
• 3 opens × 2 closes each = 6 closing brackets needed `