Longest Substring With Balanced Parentheses Problem

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.

Example One

Input: "((((())(((()"

Output: 4

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

Example Two

Input: "()()()"

Output: 6

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

Notes

Input Parameters: Function has one argument: string brackets.

Output: Function must return an integer value.

Constraints:

● 1 <= length of brackets <= 10^5

Solution

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.

1. stack_solution

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

#### START ####

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

#### STOP ####
	

2. optimal_solution.py

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.

Time Complexity:

O(n).

Auxiliary Space Used:

O(1).

Space Complexity:

O(n).

#### START ####

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

#### STOP ####