Given a string brackets that may only contain characters '(' and ')', find the length of the longest substring that has balanced parentheses.
A string is defined as having balanced parentheses if and only if it has an equal number of '(' and ')' and its every prefix has at least as many '('s as ')'s.
Return the length, not the substring.
Because "(())" is the longest substring with balanced parentheses.
The entire string "()()()" has parentheses balanced.
Input Parameters: Function has one argument: string brackets.
Output: Function must return an integer value.
A brute force solution is to find all substrings and check each one if it has balanced parentheses. Such algorithm would take O(n^3) time: n*(n-1)/2 substrings, O(n) time to check each one. We did not provide a sample implementation of this brute force algorithm.
This solution makes use of the “stack-y” (last in first out) nature of the parentheses: the last opening parenthesis is always “closed” first.
Let us see what happens if we go over the string characters from left to right.
A substring that has balanced parentheses may only end with a closing one. So any time we encounter a closing parenthesis we’d want to know if there is a matching opening one in the left part of the string. If there is, we have found a substring with balanced parentheses (then we’d want to find its length and if it’s the longest we have ever found). If there isn’t a matching opening parenthesis in the left part of the string, it means that we “closed more parentheses than opened”, the substring “so far” doesn’t have balanced parentheses and we need to “forget all about” the substring covered so far as we consider the remainder of the string (we do that by updating the valid_from variable, see below).
How do we efficiently 1) find the matching opening parenthesis to a specific closing one and 2) find the length of the current substring with balanced parentheses (once we have discovered a closing parenthesis with a matching opening one)?
We can use stack to achieve both: pushing there indices of all ‘(‘ characters and popping one back any time we encounter a ‘)’: a closing parenthesis always closes the very last opening one, so that would be the one at the top of the stack - this takes care of (1). We can observe that the latest not-yet-closed ‘(‘ is where the “current substring with balanced parentheses” starts; and we have its index right at the top of the stack at all times - this takes care of (2).
There is one special case here: when the stack is empty. To be able to efficiently find the length of the “current substring with balanced parentheses” when the stack is empty, we keep valid_from variable updated.
The algorithm makes one pass over the string with constant time calculation per character.
In the worst case there are n opening parentheses. Then we will push n items into the stack.
Input takes O(n) space, auxiliary space used: O(n). O(n)+O(n)=O(n).
We can notice that we really only care about the number of the opening and closing parentheses. In other words, unlike some other problems with more than one type of the parentheses (where “[(])” is not balanced, for example), in this problem it’s enough to count the opening and closing parentheses and keep track of their difference as we pass through the string.
Any time the number of ‘(‘s becomes equal to the number of ‘)’s we know that we have come to a point where the “balance of parentheses” is restored.
These are the main observations helping design this elegant solution which only uses constant auxiliary space. Please have a look at the source code.