Skip to content

1541. Minimum Insertions to Balance a Parentheses String

SourceBiweekly Contest 32 Q3DifficultyMediumRating1759

Description

You are given a parentheses string s containing only the characters '(' and ')'. A parentheses string is balanced if it can be formed using the following rules:

  • The empty string is balanced.
  • If A is balanced, then '(' + A + '))' is balanced.
  • If A and B are balanced, then their concatenation is balanced.

In other words, every left parenthesis '(' must have a corresponding pair of two consecutive right parentheses '))' that comes after it, and every right parenthesis must belong to exactly one such matching pair.

For example, "())", "())(())))" and "(())())))" are balanced, while ")()", "()))" 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 '(' is matched with two consecutive ')', but the first '(' has only one matching ')'. We need to insert one more ')' at the end to make the string "(())))", which is balanced.

Example 2:

Input: s = "())"

Output: 0

Explanation:

The string is already balanced because its '(' is followed by two consecutive ')', and both right parentheses belong to that matching pair.

Example 3:

Input: s = "))())("

Output: 3

Explanation:

Insert '(' at the beginning to match the first '))', and insert '))' at the end to match the last '('. Three insertions are needed in total.

 

Constraints:

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

Solutions

Solution 1

Thinking

A valid string pairs each '(' with two consecutive ')' . \(n\le 10^5\), so repeatedly rescanning insertion sites is the wrong tool; one greedy pass is enough.

Keep \(x\), the number of unmatched left parentheses. A '(' increments \(x\). On a ')', insert a mate if the next character is not also ')' . Then either insert a '(' when \(x=0\), or consume one pending left. After the scan, each leftover left needs two right parentheses.

The greedy strategy is the same as above; the Rust version only changes the scanning mechanics: a Peekable iterator consumes the matching second ')' with next_if_eq, so no explicit index bounds check is needed.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minInsertions(self, s: str) -> int:
        ans = x = 0
        i, n = 0, len(s)
        while i < n:
            if s[i] == '(':
                x += 1
            else:
                if i < n - 1 and s[i + 1] == ')':
                    i += 1
                else:
                    ans += 1
                if x == 0:
                    ans += 1
                else:
                    x -= 1
            i += 1
        ans += x << 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int minInsertions(String s) {
        int ans = 0, x = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) == '(') {
                ++x;
            } else {
                if (i < n - 1 && s.charAt(i + 1) == ')') {
                    ++i;
                } else {
                    ++ans;
                }
                if (x == 0) {
                    ++ans;
                } else {
                    --x;
                }
            }
        }
        ans += x << 1;
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int minInsertions(string s) {
        int ans = 0, x = 0;
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            if (s[i] == '(') {
                ++x;
            } else {
                if (i < n - 1 && s[i + 1] == ')') {
                    ++i;
                } else {
                    ++ans;
                }
                if (x == 0) {
                    ++ans;
                } else {
                    --x;
                }
            }
        }
        ans += x << 1;
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
func minInsertions(s string) int {
    ans, x, n := 0, 0, len(s)
    for i := 0; i < n; i++ {
        if s[i] == '(' {
            x++
        } else {
            if i < n-1 && s[i+1] == ')' {
                i++
            } else {
                ans++
            }
            if x == 0 {
                ans++
            } else {
                x--
            }
        }
    }
    ans += x << 1
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function minInsertions(s: string): number {
    let ans = 0;
    let x = 0;
    const n = s.length;
    for (let i = 0; i < n; i++) {
        if (s[i] === '(') {
            x++;
        } else {
            if (i < n - 1 && s[i + 1] === ')') {
                i++;
            } else {
                ans++;
            }
            if (x === 0) {
                ans++;
            } else {
                x--;
            }
        }
    }
    ans += x << 1;
    return ans;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
impl Solution {
    pub fn min_insertions(s: String) -> i32 {
        let mut ans = 0;
        let mut x = 0;
        let mut chars = s.bytes().peekable();
        while let Some(c) = chars.next() {
            if c == b'(' {
                x += 1;
            } else {
                if chars.next_if_eq(&b')').is_none() {
                    ans += 1;
                }
                if x == 0 {
                    ans += 1;
                } else {
                    x -= 1;
                }
            }
        }
        ans + x * 2
    }
}

Comments