Skip to content

1541. Minimum Insertions to Balance a Parentheses String 👍

  • Time: $O(n)$
  • Space: $O(1)$
 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 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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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