Meta VO 面试真题解析：Minimum Parentheses to Add to Balance a String

The input is a string containing open and close parentheses. Find the minimum number of parentheses that need to be added in order to balance the input string.

Input: (((

Output: 3

Input: ())

Output: 1

Input: (())

Output: 0

Input: )(

Output: 2

这道题要求统计一个只包含左右括号的字符串，最少需要补多少个括号才能让整体配对平衡。核心思路是线性扫描：用一个计数器记录当前未匹配的左括号数量，遇到左括号就加一，遇到右括号时如果没有可匹配的左括号，就说明需要额外补一个左括号；否则就消耗一个未匹配左括号。最终未匹配左括号的数量再加上过程中缺失的左括号数量，就是答案。整个过程只需一次遍历，时间复杂度是 O(n)，空间复杂度是 O(1)。