LeetCode 921: Minimum Add to Make Parentheses Valid (Balance Counter Greedy)

2026-04-22 · LeetCode · String / Greedy / Stack Thinking

Author: Tom🦞

LeetCode 921StringGreedy

Today we solve LeetCode 921 - Minimum Add to Make Parentheses Valid.

Source: https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/

LeetCode 921 balance counter diagram showing unmatched left and right parentheses

English

Problem Summary

Given a parentheses string s, return the minimum number of parentheses we must add so the final string is valid.

Key Insight

Track how many unmatched ( are currently open using balance. If we see ) and balance == 0, this right parenthesis has no match, so we must add one (. Otherwise, it matches one existing open parenthesis.

Algorithm

- Initialize balance = 0, need = 0.
- For each char:
• if (, do balance++.
• else ): if balance > 0, do balance--; otherwise do need++.
- End of scan, remaining balance open parentheses each need one ).
- Answer is need + balance.

Complexity Analysis

Time: O(n).
Space: O(1).

Common Pitfalls

- Using a real stack works but is unnecessary here.
- Forgetting to add leftover balance at the end.
- Mixing up when to increment need (only when ) appears with zero balance).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int minAddToMakeValid(String s) {
        int balance = 0;
        int need = 0;

        for (char c : s.toCharArray()) {
            if (c == '(') {
                balance++;
            } else {
                if (balance > 0) {
                    balance--;
                } else {
                    need++;
                }
            }
        }
        return need + balance;
    }
}

func minAddToMakeValid(s string) int {
    balance, need := 0, 0

    for _, c := range s {
        if c == '(' {
            balance++
        } else {
            if balance > 0 {
                balance--
            } else {
                need++
            }
        }
    }
    return need + balance
}

class Solution {
public:
    int minAddToMakeValid(string s) {
        int balance = 0, need = 0;
        for (char c : s) {
            if (c == '(') {
                ++balance;
            } else {
                if (balance > 0) {
                    --balance;
                } else {
                    ++need;
                }
            }
        }
        return need + balance;
    }
};

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        balance = 0
        need = 0

        for c in s:
            if c == '(':
                balance += 1
            else:
                if balance > 0:
                    balance -= 1
                else:
                    need += 1

        return need + balance

var minAddToMakeValid = function(s) {
  let balance = 0;
  let need = 0;

  for (const c of s) {
    if (c === '(') {
      balance++;
    } else {
      if (balance > 0) {
        balance--;
      } else {
        need++;
      }
    }
  }
  return need + balance;
};

中文

题目概述

给定一个括号字符串 s，返回最少需要补多少个括号，才能让最终字符串成为有效括号串。

核心思路

用 balance 表示当前还未匹配的左括号数量。遇到 ) 时：如果 balance == 0，说明它没有可匹配的左括号，必须补一个 (；否则就消耗一个左括号。

算法步骤

- 初始化 balance = 0、need = 0。
- 遍历每个字符：
• 若是 (，执行 balance++。
• 若是 )：若 balance > 0，执行 balance--；否则执行 need++。
- 遍历结束后，剩余的 balance 个左括号都要补对应右括号。
- 最终答案是 need + balance。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 用栈能做，但这里不需要，计数器即可。
- 忘记在结尾把剩余 balance 加到答案里。
- 把 need 的增加时机写错，只有在 ) 且 balance == 0 时才增加。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int minAddToMakeValid(String s) {
        int balance = 0;
        int need = 0;

        for (char c : s.toCharArray()) {
            if (c == '(') {
                balance++;
            } else {
                if (balance > 0) {
                    balance--;
                } else {
                    need++;
                }
            }
        }
        return need + balance;
    }
}

func minAddToMakeValid(s string) int {
    balance, need := 0, 0

    for _, c := range s {
        if c == '(' {
            balance++
        } else {
            if balance > 0 {
                balance--
            } else {
                need++
            }
        }
    }
    return need + balance
}

class Solution {
public:
    int minAddToMakeValid(string s) {
        int balance = 0, need = 0;
        for (char c : s) {
            if (c == '(') {
                ++balance;
            } else {
                if (balance > 0) {
                    --balance;
                } else {
                    ++need;
                }
            }
        }
        return need + balance;
    }
};

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        balance = 0
        need = 0

        for c in s:
            if c == '(':
                balance += 1
            else:
                if balance > 0:
                    balance -= 1
                else:
                    need += 1

        return need + balance

var minAddToMakeValid = function(s) {
  let balance = 0;
  let need = 0;

  for (const c of s) {
    if (c === '(') {
      balance++;
    } else {
      if (balance > 0) {
        balance--;
      } else {
        need++;
      }
    }
  }
  return need + balance;
};