Balancing parenthesis: use a counter, no need for a stack
Problems related to balancing parenthesis usually require the use of a stack, except when the problem asks for just the counter (number of movements to balance it) or when the string consists of only one type of parenthesis, say the curly brackets.
Here is an example: https://leetcode.com/problems/minimum-insertions-to-balance-a-parentheses-string/
Given a parentheses string s containing only the characters '(' and ')'. A parentheses string is balanced if:
- Any left parenthesis
'('must have a corresponding two consecutive right parenthesis'))'. - Left parenthesis
'('must go before the corresponding two consecutive right parenthesis'))'.
For example, "())", "())(())))" and "(())())))" are balanced, ")()", "()))" 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 '(' has two matching '))', but the first '(' has only ')' matching. We need to to add one more ')' at the end of the string to be "(())))" which is balanced.
Example 2:
Input: s = "())" Output: 0 Explanation: The string is already balanced.
Example 3:
Input: s = "))())(" Output: 3 Explanation: Add '(' to match the first '))', Add '))' to match the last '('.
Example 4:
Input: s = "((((((" Output: 12 Explanation: Add 12 ')' to balance the string.
Example 5:
Input: s = ")))))))" Output: 5 Explanation: Add 4 '(' at the beginning of the string and one ')' at the end. The string becomes "(((())))))))".
Constraints:
1 <= s.length <= 10^5sconsists of'('and')'only.
The solution to this problem isn't particular pretty since I had to go thru the numerous corner cases and state machines, but it works in O(n)-time and uses just the counters. The key point for me was to follow the different cases in close details, taking care of the two overall counters (retVal and numOpen) as well as controlling the iterator inside the loop whenever necessary. Code is below. And you can also take a sneak peek of me running on Pacific Beach, near Oregon. Cheers, ACC.
public int MinInsertions(string s)
{
if (String.IsNullOrEmpty(s)) return 0;
int retVal = 0;
int numOpen = 0;
for (int i = 0; i < s.Length; i++)
{
if (s[i] == '(')
{
numOpen++;
}
else //s[i] == ')'
{
if (i == s.Length - 1) //Last
{
retVal++;
if (numOpen > 0)
{
numOpen--;
}
else
{
retVal++;
}
}
else
{
if (s[i + 1] == ')')
{
if (numOpen > 0)
{
numOpen--;
}
else
{
retVal++;
}
i++;
}
else
{
if (numOpen > 0)
{
numOpen--;
retVal++;
}
else
{
retVal += 2;
}
}
}
}
}
return retVal + (2 * numOpen);
}
Comments
Post a Comment
[γγ¬γΌγ ]