Given a string brackets that only contains characters '(' and ')', find the length of the longest substring that has "balanced parentheses".
{
"brackets": "((((())(((()"
}
Output:
4
Because "(())" is the longest substring with balanced parentheses.
{
"balanced": "()()()"
}
Output:
6
The entire string "()()()" has parentheses balanced.
'(' and ')' and its every prefix has at least as many '('s as ')'s.Constraints:
brackets <= 105A brute force solution is to find all substrings and check each one if it has balanced parentheses. Such algorithm would take O(n3) 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.
O(n).
The algorithm makes one pass over the string with constant time calculation per character.
O(n).
In the worst case there are n opening parentheses. Then we will push n items into the stack.
O(n).
Input takes O(n) space, auxiliary space used: O(n). O(n) + O(n) = O(n).
"""
* Asymptotic complexity in terms of length of \`brackets\` \`n\`:
* Time: O(n).
* Auxiliary space: O(n).
* Total space: O(n).
"""
def find_max_length_of_matching_parentheses(brackets):
# Indices of the opening parentheses will be pushed into the stack and popped back out
# once the matching closing parenthesis found. The latest not-yet-closed '(' is always
# at the top of the stack, that is where current substring with balanced parentheses begins.
stack = []
# Starting index of the current substring with balanced parentheses when the stack is empty.
valid_from = 0
# The longest substring with balanced parentheses we found so far:
max_length = 0
for i, bracket in enumerate(brackets):
if bracket == '(':
stack.append(i)
else:
if not stack:
# We found a closing parenthesis with no matching opening one.
# It means that the substring until and including current index DOES NOT have
# balanced parentheses and we must "forget about" it until the end of the string.
valid_from = i + 1
else:
# We found a closing parenthesis with a matching opening one.
# It means that the substring ending at the current index i DOES have balanced parentheses.
# Let us see if it is longer than max_length.
stack.pop()
substring_start = valid_from - 1 if not stack else stack[-1]
substring_length = i - substring_start
max_length = max(substring_length, max_length)
return max_length
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.
O(n).
O(1).
O(n).
"""
* Asymptotic complexity in terms of length of \`brackets\` \`n\`:
* Time: O(n).
* Auxiliary space: O(1).
* Total space: O(n).
"""
def find_max_length_of_matching_parentheses(brackets):
n = len(brackets)
max_length = 0
# Scan from left to right.
left_count = right_count = 0
for idx in range(n):
if brackets[idx] == '(':
left_count += 1
else:
right_count += 1
if left_count < right_count:
left_count = right_count = 0
elif left_count == right_count:
max_length = max(max_length, 2 * left_count)
"""
Consider '(((()))'.
First 'left_count' becomes 4, then 'right_count' becomes 3. The "balance" of left_count==right_count
is never reached, so answer is not found. A scan in the opposite direction is needed.
"""
# Scan from right to left.
left_count = right_count = 0
for idx in range(n - 1, -1, -1):
if brackets[idx] == '(':
left_count += 1
else:
right_count += 1
if left_count > right_count:
left_count = right_count = 0
elif left_count == right_count:
max_length = max(max_length, 2 * left_count)
return max_length
We hope that these solutions to longest substring with balanced parentheses have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.
If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart's FREE webinar to understand the best way to prepare.
Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.
We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:
To learn more, register for the FREE webinar.
