Katkat
Back

Longest Balanced Substring in a String of Parentheses

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

A Meta coding interview problem: given a string made only of opening and closing parentheses, return the length of the longest contiguous substring that is correctly balanced. It tests careful handling of matched pairs, unmatched characters that break a run, and efficient processing of long inputs.

Reported from a Meta software engineering coding round.

You are given a string s that contains only the characters ( and ). A string is balanced if it can be built with these rules:

  • the empty string is balanced;
  • if A is balanced, then (A) is balanced;
  • if A and B are balanced, then their concatenation AB is balanced.

Return the length of the longest non-empty contiguous substring of s that is balanced. If s has no such substring, return 0.

Function Signature

def longest_balanced_substring(s: str) -> int:

Rules

  • Only contiguous substrings count; characters may not be skipped.
  • The result is a single integer (a length), so it is unique even when several substrings share the maximum length.

Constraints

  • 0 <= len(s) <= 3 * 10^4
  • Every character of s is ( or ).
  • The answer is at most len(s), well inside the 32-bit signed integer range.

Examples

Example 1

  • Input: s = ")(())()"
  • Output: 6
  • Explanation: the substring "(())()" starting at index 1 is balanced. The leading ) cannot belong to any balanced substring.

Example 2

  • Input: s = "()(()"
  • Output: 2
  • Explanation: "()" at indices 0-1 and "()" at indices 3-4 are balanced, but the unmatched ( at index 2 sits between them, so nothing longer is balanced.

Example 3

  • Input: s = "))(("
  • Output: 0
  • Explanation: no non-empty substring is balanced.