Maximal balanced parentheses length

You're in a Google phone screen and the interviewer asks you to find the longest valid parentheses substring. You know how to check whether a string of parentheses is balanced, but this is different. The string ")()())" is clearly not balanced overall, yet it contains "()()" as a valid substring of length 4. Finding that longest valid piece is the real challenge, and it is also known as the "Longest Valid Parentheses" problem on other platforms. This problem tests your ability to move from brute-force thinking to a clean, constant-space linear scan.

TL;DR

Use a two-pass counter technique. Scan left-to-right, counting opening and closing parentheses. When the counts match, you have a valid substring, so update the maximum. When closing exceeds opening, reset both counters. Then repeat the scan right-to-left with the reset condition flipped. This handles every edge case in O(n) time and O(1) space.

Why This Problem Matters

Parentheses problems are a staple in technical interviews because they test your understanding of string scanning, stack manipulation, and dynamic programming all at once. The "longest valid parentheses" variant is a step up from basic bracket matching. It asks you to find the longest contiguous well-formed piece, not just check overall validity. Companies like Uber, Google, and Bloomberg use it precisely because it has multiple valid approaches, each with different space-time tradeoffs, and the interviewer can gauge your depth based on which one you reach.

Understanding the Problem

Given a string s consisting only of '(' and ')', find the length of the longest substring that forms valid, well-formed parentheses.

Examples:

longestValidParentheses("(()") => 2
  The longest valid substring is "()", starting at index 1.

longestValidParentheses(")()())") => 4
  The longest valid substring is "()()", starting at index 1.

longestValidParentheses("") => 0
  No characters means no valid parentheses.

A few things to note. The problem asks for a substring (contiguous characters), not a subsequence. The string "(()" is not fully valid, but the last two characters "()" form a valid substring of length 2. For ")()())", the valid substring "()()" spans indices 1 through 4.

Edge Cases

1. Empty string: Return 0 immediately.
2. All opening: "(((((" has no valid pairs, so the answer is 0.
3. All closing: "))))))" also returns 0.
4. Fully matched: "((()))" returns 6, the entire string.
5. Multiple valid sections: "()()" returns 4. The two pairs combine into one valid substring.

Constraints

• 0 ≤ s.length ≤ 10^4
• Each character s[i] is either '(' or ')'.

Why Brute Force Falls Short

The naive approach checks every possible substring, validates it, and tracks the longest valid one. For a string of length n, there are O(n^2) substrings, and validating each takes O(n) time. That gives O(n^3) total, which is far too slow for strings up to 10,000 characters. We need something linear.

The Two-Pass Counter Technique

The key insight is that we can detect valid parentheses substrings by counting. If we scan left-to-right and maintain a left counter for '(' and a right counter for ')', then whenever left == right, the characters we have seen since the last reset form a valid substring.

But there is a catch. If the string has excess opening parentheses (like "(()") then left always exceeds right, and the counters never become equal. The left-to-right pass misses these cases entirely.

That is why we need a second pass, going right-to-left with the reset condition flipped. In the reverse pass, we reset when left exceeds right instead. This catches the cases the first pass misses.

Pass 1: Left to Right

Scan the string from index 0 to n-1:

• If the character is '(', increment left.
• If the character is ')', increment right.
• When left == right, update maxLength with 2 * right (the total matched length).
• When right exceeds left, we have an unbalanced closing paren, so reset both counters to 0.

Let's trace through "(()":

After the left-to-right pass, maxLength is still 0 because left (which reached 2) never equaled right (which reached 1). The valid substring "()" at positions 1-2 was not detected.

Pass 2: Right to Left

Now scan from index n-1 back to 0:

• Count the same way (incrementing left for '(' and right for ')').
• When left == right, update maxLength with 2 * left.
• When left exceeds right, reset both counters to 0.

Tracing "(()" right-to-left:

The reverse pass finds the valid substring of length 2. The final answer is max(0, 2) = 2.

Full Walkthrough: ")()())"

Let's trace the more complex example with the left-to-right pass:

The first ) at index 0 causes an immediate reset (right exceeds left). Then "()" at indices 1-2 gives maxLength = 2. Continuing, "()" at indices 3-4 extends the matched region, and at index 4 we get left == right == 2, giving maxLength = 4. The final ) at index 5 causes another reset. No improvement comes from the right-to-left pass in this case, so the answer is 4.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public int longestValidParentheses(String s) {
    int maxLength = 0;
    int left = 0, right = 0;

    // Pass 1: Left to right
    for (int i = 0; i < s.length(); i++) {
      if (s.charAt(i) == '(') {
        left++;
      } else {
        right++;
      }
      if (left == right) {
        maxLength = Math.max(maxLength, 2 * right);
      } else if (right > left) {
        left = 0;
        right = 0;
      }
    }

    // Pass 2: Right to left
    left = 0;
    right = 0;

    for (int i = s.length() - 1; i >= 0; i--) {
      if (s.charAt(i) == '(') {
        left++;
      } else {
        right++;
      }
      if (left == right) {
        maxLength = Math.max(maxLength, 2 * left);
      } else if (left > right) {
        left = 0;
        right = 0;
      }
    }

    return maxLength;
  }
}

Walking Through the Code

The structure is straightforward. We declare three variables: maxLength, left, and right. The first loop scans left-to-right. At each character, we increment the appropriate counter. When the counters match, we know that every '(' has been paired with a ')' since the last reset, so 2 * right gives the valid length. When right exceeds left, we have an unrecoverable excess of closing parens, so we start fresh.

After the first pass, we zero out left and right and repeat in the opposite direction. The only change is the reset condition: now we reset when left exceeds right, because an excess of opening parens means the right-to-left scan has hit an unrecoverable imbalance.

The maxLength variable carries over between passes. The final value is the answer.

Complexity Analysis

Time Complexity: O(n)

Each pass visits every character exactly once, and we make two passes. That gives 2n character accesses, which is O(n). The work per character is constant: one comparison, one or two increments, and possibly one max computation.

Space Complexity: O(1)

We use exactly three integer variables regardless of input size. No arrays, no stacks, no hash maps. This is optimal since we must at least read the input.

Alternative Approaches

There are two other well-known solutions for this problem:

1. Stack-based (O(n) time, O(n) space): Push indices onto a stack. For each ')', pop and compute the length from the current index minus the new stack top. A sentinel index at the bottom handles the boundary.

2. Dynamic programming (O(n) time, O(n) space): Build a dp array where dp[i] is the length of the longest valid substring ending at index i. When s[i] is ')', check if it pairs with a '(' and extend any valid substring immediately before it.

Both are valid interview answers. The two-pass approach we covered is optimal on space, which is a nice point to mention when discussing tradeoffs.

Common Pitfalls

1. Only scanning one direction: A single left-to-right pass fails on inputs like "(()" where opening parens dominate. You need the second pass.

2. Resetting on the wrong condition: In the left-to-right pass, reset when right > left. In the right-to-left pass, reset when left > right. Mixing these up gives incorrect results.

3. Using 2 * right vs 2 * left: In the left-to-right pass, the valid length is 2 * right (since right counts the closing parens that completed matches). In the right-to-left pass, use 2 * left (since left plays the analogous role). Getting this wrong produces off-by-one style errors.

4. Forgetting to reset between passes: The left and right counters must be zeroed before the second pass starts.

Interview Tips

When you encounter this problem in an interview:

1. Start with clarifying questions: "Is this the longest contiguous substring, or a subsequence?" and "Can the string be empty?"

2. Mention the brute-force first: Briefly explain the O(n^3) approach to show you understand the problem, then say you will optimize.

3. If you know the stack approach, start there: The stack solution is often easier to implement correctly under pressure. Once it works, offer the two-pass optimization as a follow-up.

4. Draw out the counter states: Showing how left and right evolve on a whiteboard makes the two-pass logic much clearer.

5. Discuss tradeoffs: "The stack approach is O(n) time and O(n) space. The two-pass approach trades simplicity for O(1) space. Which would you prefer I implement?"

Key Takeaways

• The two-pass counter technique achieves O(n) time and O(1) space by scanning left-to-right then right-to-left, resetting counters when the trailing paren type exceeds the leading one.
• A single pass is not enough because excess opening parentheses prevent the counters from ever becoming equal, hiding valid substrings that the reverse pass detects.
• When left == right, the total valid length since the last reset is 2 * right (left-to-right) or 2 * left (right-to-left), because each matched pair contributes 2 to the length.
• The stack and DP approaches both solve this in O(n) time with O(n) space. Knowing all three and their tradeoffs signals strong algorithmic depth in an interview.
• Test with "(()", ")()())", and "" to cover the main edge cases: excess opens, excess closes, and empty input.

Practice and Related Problems

Once you are comfortable with this problem, try these related challenges to build on the same patterns:

• Bracket Harmony Check (problem 167): The simpler "are these parentheses valid?" problem that serves as a warm-up.
• Wildcard Parenthesis Validator (problem 825): Adds wildcard characters that can act as either paren or empty.
• Generate Combinations of Parentheses (problem 61): Generates all valid strings of n pairs, testing the same structural understanding from the other direction.

This problem and hundreds more are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top companies. Consistent practice with problems like this builds the pattern recognition you need to perform under pressure.

Solutions in Other Languages

Python

class Solution:
    def longest_valid_parentheses(self, s: str) -> int:
        max_length = 0
        left = 0
        right = 0

        for char in s:
            if char == '(':
                left += 1
            else:
                right += 1
            if left == right:
                max_length = max(max_length, 2 * right)
            elif right > left:
                left = 0
                right = 0

        left = 0
        right = 0

        for i in range(len(s) - 1, -1, -1):
            if s[i] == '(':
                left += 1
            else:
                right += 1
            if left == right:
                max_length = max(max_length, 2 * left)
            elif left > right:
                left = 0
                right = 0

        return max_length

JavaScript

class Solution {
  longestValidParentheses(s) {
    let maxLength = 0;
    let left = 0, right = 0;

    for (let i = 0; i < s.length; i++) {
      if (s[i] === '(') left++;
      else right++;
      if (left === right) maxLength = Math.max(maxLength, 2 * right);
      else if (right > left) { left = 0; right = 0; }
    }

    left = 0; right = 0;

    for (let i = s.length - 1; i >= 0; i--) {
      if (s[i] === '(') left++;
      else right++;
      if (left === right) maxLength = Math.max(maxLength, 2 * left);
      else if (left > right) { left = 0; right = 0; }
    }

    return maxLength;
  }
}

TypeScript

class Solution {
  longestValidParentheses(s: string): number {
    let maxLength = 0;
    let left = 0, right = 0;

    for (let i = 0; i < s.length; i++) {
      if (s[i] === '(') left++;
      else right++;
      if (left === right) maxLength = Math.max(maxLength, 2 * right);
      else if (right > left) { left = 0; right = 0; }
    }

    left = 0; right = 0;

    for (let i = s.length - 1; i >= 0; i--) {
      if (s[i] === '(') left++;
      else right++;
      if (left === right) maxLength = Math.max(maxLength, 2 * left);
      else if (left > right) { left = 0; right = 0; }
    }

    return maxLength;
  }
}

C++

#include <string>
#include <algorithm>

class Solution {
public:
    int longestValidParentheses(std::string s) {
        int maxLength = 0;
        int left = 0, right = 0;

        for (int i = 0; i < s.length(); ++i) {
            if (s[i] == '(') left++;
            else right++;
            if (left == right) maxLength = std::max(maxLength, 2 * right);
            else if (right > left) { left = 0; right = 0; }
        }

        left = 0; right = 0;

        for (int i = s.length() - 1; i >= 0; --i) {
            if (s[i] == '(') left++;
            else right++;
            if (left == right) maxLength = std::max(maxLength, 2 * left);
            else if (left > right) { left = 0; right = 0; }
        }

        return maxLength;
    }
};

Scala

class Solution {
  def longestValidParentheses(s: String): Int = {
    var maxLength = 0
    var left = 0
    var right = 0

    for (char <- s) {
      if (char == '(') left += 1 else right += 1
      if (left == right) maxLength = math.max(maxLength, 2 * right)
      else if (right > left) { left = 0; right = 0 }
    }

    left = 0; right = 0

    for (i <- s.length - 1 to 0 by -1) {
      if (s(i) == '(') left += 1 else right += 1
      if (left == right) maxLength = math.max(maxLength, 2 * left)
      else if (left > right) { left = 0; right = 0 }
    }

    maxLength
  }
}

Kotlin

class Solution {
  fun longestValidParentheses(s: String): Int {
    var maxLength = 0
    var left = 0
    var right = 0

    for (i in s.indices) {
      if (s[i] == '(') left++ else right++
      if (left == right) maxLength = maxOf(maxLength, 2 * right)
      else if (right > left) { left = 0; right = 0 }
    }

    left = 0; right = 0

    for (i in s.lastIndex downTo 0) {
      if (s[i] == '(') left++ else right++
      if (left == right) maxLength = maxOf(maxLength, 2 * left)
      else if (left > right) { left = 0; right = 0 }
    }

    return maxLength
  }
}

Swift

class Solution {
    func longestValidParentheses(_ s: String) -> Int {
        var maxLength = 0
        var left = 0
        var right = 0
        let chars = Array(s)

        for i in 0..<chars.count {
            if chars[i] == Character("(") { left += 1 } else { right += 1 }
            if left == right { maxLength = max(maxLength, 2 * right) }
            else if right > left { left = 0; right = 0 }
        }

        left = 0; right = 0

        for i in stride(from: chars.count - 1, through: 0, by: -1) {
            if chars[i] == Character("(") { left += 1 } else { right += 1 }
            if left == right { maxLength = max(maxLength, 2 * left) }
            else if left > right { left = 0; right = 0 }
        }

        return maxLength
    }
}

Rust

pub struct Solution;

impl Solution {
    pub fn longest_valid_parentheses(&self, s: String) -> i32 {
        let mut max_length = 0;
        let mut left = 0;
        let mut right = 0;
        let chars: Vec<char> = s.chars().collect();

        for i in 0..chars.len() {
            if chars[i] == '(' { left += 1; } else { right += 1; }
            if left == right { max_length = max_length.max(2 * right); }
            else if right > left { left = 0; right = 0; }
        }

        left = 0; right = 0;

        for i in (0..chars.len()).rev() {
            if chars[i] == '(' { left += 1; } else { right += 1; }
            if left == right { max_length = max_length.max(2 * left); }
            else if left > right { left = 0; right = 0; }
        }

        max_length
    }
}

C#

public class Solution {
    public int longestValidParentheses(string s) {
        int maxLength = 0;
        int left = 0, right = 0;

        for (int i = 0; i < s.Length; i++) {
            if (s[i] == '(') left++;
            else right++;
            if (left == right) maxLength = Math.Max(maxLength, 2 * right);
            else if (right > left) { left = 0; right = 0; }
        }

        left = 0; right = 0;

        for (int i = s.Length - 1; i >= 0; i--) {
            if (s[i] == '(') left++;
            else right++;
            if (left == right) maxLength = Math.Max(maxLength, 2 * left);
            else if (left > right) { left = 0; right = 0; }
        }

        return maxLength;
    }
}

Dart

import 'dart:math';

class Solution {
  int longestValidParentheses(String s) {
    int maxLength = 0;
    int left = 0, right = 0;

    for (int i = 0; i < s.length; i++) {
      if (s[i] == '(') left++;
      else right++;
      if (left == right) maxLength = max(maxLength, 2 * right);
      else if (right > left) { left = 0; right = 0; }
    }

    left = 0; right = 0;

    for (int i = s.length - 1; i >= 0; i--) {
      if (s[i] == '(') left++;
      else right++;
      if (left == right) maxLength = max(maxLength, 2 * left);
      else if (left > right) { left = 0; right = 0; }
    }

    return maxLength;
  }
}

PHP

class Solution {
    public function longestValidParentheses(string $s): int {
        $maxLength = 0;
        $left = 0;
        $right = 0;

        for ($i = 0; $i < strlen($s); $i++) {
            if ($s[$i] === '(') $left++;
            else $right++;
            if ($left === $right) $maxLength = max($maxLength, 2 * $right);
            elseif ($right > $left) { $left = 0; $right = 0; }
        }

        $left = 0; $right = 0;

        for ($i = strlen($s) - 1; $i >= 0; $i--) {
            if ($s[$i] === '(') $left++;
            else $right++;
            if ($left === $right) $maxLength = max($maxLength, 2 * $left);
            elseif ($left > $right) { $left = 0; $right = 0; }
        }

        return $maxLength;
    }
}

Ruby

class Solution
  def longest_valid_parentheses(s)
    max_length = 0
    left = 0
    right = 0

    s.each_char do |char|
      if char == '('
        left += 1
      else
        right += 1
      end
      if left == right
        max_length = [max_length, 2 * right].max
      elsif right > left
        left = 0
        right = 0
      end
    end

    left = 0
    right = 0

    s.reverse.each_char do |char|
      if char == '('
        left += 1
      else
        right += 1
      end
      if left == right
        max_length = [max_length, 2 * left].max
      elsif left > right
        left = 0
        right = 0
      end
    end

    max_length
  end
end