Register for our webinar

### How to Nail your next Technical Interview

1 hour
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
Step 1
Step 2
Congratulations!
You have registered for our webinar
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.

## You may be missing out on a 66.5% salary hike*

### Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Help us know you better!

## How many years of coding experience do you have?

Oops! Something went wrong while submitting the form.

## FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Oops! Something went wrong while submitting the form.

# Longest Substring With Balanced Parentheses Problem Statement

Given a string `brackets` that only contains characters `'('` and `')'`, find the length of the longest substring that has "balanced parentheses".

## Example One

``````{
"brackets": "((((())(((()"
}
``````

Output:

``````4
``````

Because `"(())"` is the longest substring with balanced parentheses.

## Example Two

``````{
"balanced": "()()()"
}
``````

Output:

``````6
``````

The entire string `"()()()"` has parentheses balanced.

## Notes

• 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.

Constraints:

• 1 <= length of `brackets` <= 105

A 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.

# Longest Substring With Balanced Parentheses Solution 1: Stack

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.

## Time Complexity

O(n).

The algorithm makes one pass over the string with constant time calculation per character.

## Auxiliary Space Used

O(n).

In the worst case there are `n` opening parentheses. Then we will push `n` items into the stack.

## Space Complexity

O(n).

Input takes O(n) space, auxiliary space used: O(n). O(n) + O(n) = O(n).

## Code For Longest Substring With Balanced Parentheses Solution 1: Stack

``````"""
* 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

``````

# Longest Substring With Balanced Parentheses Solution 2: Optimal

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).

## Code For Longest Substring With Balanced Parentheses Solution 2: Optimal

``````"""
* 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
"""

# 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:

### Try yourself in the Editor

Note: Input and Output will already be taken care of.

# Longest Substring With Balanced Parentheses Problem Statement

Given a string `brackets` that only contains characters `'('` and `')'`, find the length of the longest substring that has "balanced parentheses".

## Example One

``````{
"brackets": "((((())(((()"
}
``````

Output:

``````4
``````

Because `"(())"` is the longest substring with balanced parentheses.

## Example Two

``````{
"balanced": "()()()"
}
``````

Output:

``````6
``````

The entire string `"()()()"` has parentheses balanced.

## Notes

• 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.

Constraints:

• 1 <= length of `brackets` <= 105

A 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.

# Longest Substring With Balanced Parentheses Solution 1: Stack

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.

## Time Complexity

O(n).

The algorithm makes one pass over the string with constant time calculation per character.

## Auxiliary Space Used

O(n).

In the worst case there are `n` opening parentheses. Then we will push `n` items into the stack.

## Space Complexity

O(n).

Input takes O(n) space, auxiliary space used: O(n). O(n) + O(n) = O(n).

## Code For Longest Substring With Balanced Parentheses Solution 1: Stack

``````"""
* 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

``````

# Longest Substring With Balanced Parentheses Solution 2: Optimal

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).

## Code For Longest Substring With Balanced Parentheses Solution 2: Optimal

``````"""
* 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
"""

# 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: