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
This problem asks for the minimum number of parentheses that must be added to make a string of parentheses balanced. The standard solution scans the string once while tracking unmatched left parentheses: increase the balance for '(' and, for ')', either match one existing '(' or count one needed opening parenthesis when none is available. After the scan, any remaining unmatched '(' are also added to the result. The approach is O(n) time and O(1) space.
END
