Longest Balanced Substring

Tags

Longest Balanced Substring

Category

Strings

Difficulty

Hard

Problem Statement

Given a string consisting of only ( and ) characters, find the length of the longest contiguous substring that has balanced (valid) parentheses. A balanced substring has every opening parenthesis matched with a corresponding closing parenthesis in the correct order.

Intuition

A stack-based approach naturally handles parenthesis matching. By pushing indices onto the stack, we can compute the length of valid substrings when we find matching pairs. The key insight is to keep the index of the last unmatched position on the stack as a reference point. Alternatively, a two-pass approach (left-to-right and right-to-left) with counters avoids extra space entirely.

Approach

Stack-Based Approach

  1. Initialize a stack with -1 (as a base for length calculations).
  2. Iterate through the string: a. If the character is (, push its index onto the stack. b. If the character is ):
    • Pop from the stack.
    • If the stack is now empty, push the current index as the new base.
    • Otherwise, compute the length as currentIndex - stack.top() and update the maximum.
  3. Return the maximum length.

Two-Pass Approach (O(1) Space)

  1. Left-to-right: Track open and close counters. When they are equal, record the length. When close > open, reset both to 0.
  2. Right-to-left: Track open and close counters. When they are equal, record the length. When open > close, reset both to 0.
  3. Return the maximum length found across both passes.

Pseudocode

// Stack approach
function longestBalancedSubstring(string):
    maxLength = 0
    stack = [-1]

    for i from 0 to length(string) - 1:
        if string[i] == '(':
            stack.push(i)
        else:
            stack.pop()
            if stack is empty:
                stack.push(i)
            else:
                maxLength = max(maxLength, i - stack.top())

    return maxLength

// Two-pass approach
function longestBalancedSubstring(string):
    maxLength = 0

    // Left to right
    open = 0, close = 0
    for char in string:
        if char == '(': open++
        else: close++
        if open == close:
            maxLength = max(maxLength, 2 * close)
        if close > open:
            open = 0; close = 0

    // Right to left
    open = 0, close = 0
    for char in reverse(string):
        if char == '(': open++
        else: close++
        if open == close:
            maxLength = max(maxLength, 2 * open)
        if open > close:
            open = 0; close = 0

    return maxLength

Time & Space Complexity

  • Stack approach: O(n) time, O(n) space.
  • Two-pass approach: O(n) time, O(1) space.

Both approaches make a constant number of passes through the string.

Key Insights

  • The stack stores indices, not characters. This is essential for computing substring lengths.
  • Initializing the stack with -1 handles the case where a valid substring starts at index 0.
  • The two-pass approach is needed because a single left-to-right pass cannot detect the longest balanced substring ending with excess opening parentheses (e.g., (()). The reverse pass catches these cases.
  • The problem is equivalent to finding the longest valid parentheses, a classic dynamic programming and stack problem.

Edge Cases

  • Empty string: return 0.
  • No valid pairs (e.g., )))(): return 0.
  • Entire string is balanced: return the full length.
  • Single character: return 0.
  • Nested balanced substrings (e.g., (())): the entire string is the answer.
  • Adjacent balanced substrings (e.g., ()()): the combined length is the answer.

Linked mentions