Longest Balanced Substring | Maximum Length of Balanced Parentheses

You have given a string that contains the curly braces (brackets), both opening and closing braces. You have to find the length of the longest balanced subarray.

Example:

Input : {}{}{
Output: 4

Explanation:

In the above example, the length of the longest subarray/substring is four ({}{}) .

There can be multiple balanced subarrays. In that case, you have to return the length of the longest balanced (valid) subarray.

This coding question was asked in the Bright Money coding test.

Note: Sometimes, there can be parenthesis or square brackets instead of curly braces.

Algorithm

• Step 1:
  – Initialize the stack (says tack_braces) to check the balanced braces. (Push the character when it is { and pop it when the character is }).
• Step 2:
  – Maintain the list (says list_count) for counting the length of all the balance substrings.
• Step 3:
  – Loop over all the characters (says ch) in the string of opening and closing braces.
• Step 3.2:
  – If the character ch is opening a brace {, add into the stack.
  – If the character ch is } and the stack is not empty, increment the counter by one.
  – If the character ch is } and the stack is empty (That means, it is no longer balanced.), append the count to list_count.
• Step 3.3:
  – Return the maximum length among all the balanced subarray lengths, multiply by two.

If you understand the logic described in the above algorithm, you can solve this problem in any programming language of your choice.

Python Program for Longest Balanced Substring

We can use the list as a stack in Python. Python list method pop(), remove the last element from the list.

Code:

def max_length_balanced_braces(str_braces):
    stack_braces = []
    list_count = []
    count = 0
    for ch in str_braces:
        if ch == "{":
            stack_braces.append(ch)
        elif stack_braces:
            count += 1
            stack_braces.pop()
        else:
            list_count.append(count)
            count = 0
    return max(list_count)*2

braces = "{}{}}"
count = max_length_balanced_braces(braces)
print(f"Maximum length of balanced substring {braces} is {count}")
 
braces = "{}{{}}}}}"
count = max_length_balanced_braces(braces)
print(f"Maximum length of balanced substring {braces} is {count}"

Output:

Maximum length of balanced substring {}{}} is 4
Maximum length of balanced substring {}{{}}}}} is 6

Complexity

As we are visiting each character in the given string only once, the complexity of the algorithm is O(n). Where, n is the length of the string.

I have solved this in Python programming language. Can anyone solve this in C/C++ or Java programming language? Let’s share your solution to find the longest balanced substring/parenthesis in the comment section below.