Longest valid bracket substring with nesting ranks: Frontier Interview's solution

Question: Longest valid bracket substring with nesting ranks

Companies: Uber

Difficulty: Hard

Problem statement

Given a string made only of the characters (, ), [, ], { and }, return the length of the longest contiguous substring that is valid.

A string is valid when all of these hold:

Every bracket is closed by a bracket of the same kind, and pairs close in the right order (ordinary balanced brackets).
The kinds have a rank: curly {} is highest, square [] is in the middle, and round () is lowest. A pair may directly contain pairs of the same or lower rank only. So {[()]}, {{}} and [()()] are valid, but ([]) and [{}] are not.
Concatenating valid strings gives a valid string, in any order. For example, ()[]{} is valid.

def longest_valid(s: str) -> int: ...

Return 0 if no valid substring exists.

Constraints: 0 <= len(s) <= 10^5. Aim for O(n) time.

Example 1. s = "){[()]}[]((" returns 8, for the substring "{[()]}[]".

Example 2. s = "({}[()])" returns 6. The string is balanced, but ( may not contain { or [, so the outer pair is not valid. The longest valid substring is "{}[()]".

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

This is LeetCode 32 (longest valid parentheses) with two extra rules. There are three bracket kinds, and they have a rank: curly {} is outermost, square [] is in the middle, and round () is innermost. A pair may directly contain pairs of the same rank or a lower rank, but never a higher one. So {[()]}, [[()]] and {{}} are valid. ([]) and [{}] are not, even though they are balanced.

Brute force. Check every substring with a stack validator. A matching closer must pop its opener, and a new opener's rank must not exceed the rank of the opener on top of the stack. That is O(n^2) substrings times O(n) to check each, so O(n^3). It is worth stating, and it is the oracle for randomized tests.

One pass with a stack of indices. This is the classic LC 32 stack, plus one new kind of reset.

The stack always holds a base at the bottom. The base is the index just before the earliest position where a valid substring could start right now. It starts at -1. Every entry above the base is a live opener, meaning an opener that can still be matched.
Matching closer. If the top is a live opener of the same kind, pop it. The substring from stack[-1] + 1 to i is now valid, so record i - stack[-1] as a candidate length.
Bad closer. The closer has nothing to match, or the top opener is a different kind. No valid substring can cross this position, so reset the stack to [i].
Opener that breaks the nesting rule. For example, { arrives while ( is the innermost live opener. If that ( were ever closed, it would contain the {, which is not allowed. The same holds for every live opener below it, because each of them encloses the (. So all live openers are dead. A valid substring can still start right after the innermost one, for example []{} inside ([]{}). So the innermost opener becomes the new base, and we push i: stack = [top, i].
Legal opener. Push its index.

Invariant. Openers above the base form a chain where rank never goes up from bottom to top. Everything between two neighboring stack entries is a concatenation of valid blocks. That is why i - stack[-1] after a pop is the length of a valid substring. It is also the longest valid substring that ends at i, because the base is the hard left wall. We only need to check the new opener against its direct parent. The chain is already monotone, so the check holds for every ancestor too.

Code

from typing import List, Tuple

RANK = {"(": 1, "[": 2, "{": 3}
MATCH = {")": "(", "]": "[", "}": "{"}


def longest_valid_span(s: str) -> Tuple[int, int]:
    """Return (start, length) of the leftmost longest valid substring.

    Valid = balanced, same-kind matching, and no pair directly contains a
    pair of higher rank ({ > [ > ( ). Length 0 means none exists.
    """
    stack: List[int] = [-1]  # stack[0] is the base; the rest are live openers
    best_start, best_len = 0, 0
    for i, c in enumerate(s):
        if c in RANK:
            if len(stack) > 1 and RANK[c] > RANK[s[stack[-1]]]:
                # c cannot sit inside any live opener; they all die. The
                # innermost one becomes the new left wall.
                stack = [stack[-1], i]
            else:
                stack.append(i)
        elif c in MATCH:
            if len(stack) > 1 and s[stack[-1]] == MATCH[c]:
                stack.pop()
                length = i - stack[-1]
                if length > best_len:
                    best_start, best_len = stack[-1] + 1, length
            else:
                stack = [i]  # unmatched or mismatched closer: hard wall
        else:
            raise ValueError(f"unexpected character {c!r} at {i}")
    return best_start, best_len


def longest_valid(s: str) -> int:
    return longest_valid_span(s)[1]


def is_valid(s: str) -> bool:
    """Full-string validator with the nesting rule (used by the brute force)."""
    stack: List[str] = []
    for c in s:
        if c in RANK:
            if stack and RANK[c] > RANK[stack[-1]]:
                return False
            stack.append(c)
        else:
            if not stack or stack[-1] != MATCH[c]:
                return False
            stack.pop()
    return not stack


def longest_valid_brute(s: str) -> int:
    n, best = len(s), 0
    for i in range(n):
        for j in range(i + 2, n + 1, 2):
            if j - i > best and is_valid(s[i:j]):
                best = j - i
    return best


if __name__ == "__main__":
    import random

    assert longest_valid("") == 0
    assert longest_valid("{[()]}") == 6
    assert longest_valid("([])") == 2            # "[]" only; ( cannot hold [
    assert longest_valid("([]{})") == 4          # "[]{}"
    assert longest_valid(")()())") == 4
    assert longest_valid("{[}]") == 0
    assert longest_valid("[(])") == 0
    assert longest_valid("{}[]()") == 6
    assert longest_valid("{{}}[[()]]") == 10
    assert longest_valid("(()[[]]") == 6         # "()[[]]"
    assert longest_valid_span("{}") == (0, 2)
    assert longest_valid_span(")){[]}(") == (2, 4)

    for _ in range(3000):
        t = "".join(random.choice("()[]{}") for _ in range(random.randint(0, 14)))
        assert longest_valid(t) == longest_valid_brute(t), t
    print("ok")

Complexity

Time: O(n). Each index is pushed at most once and popped or discarded at most once.
Space: O(n) for the stack in the worst case, for example {{{{….
The brute force is O(n^3) time and O(n) space.

Test cases

"" → 0
"{[()]}" → 6, the whole string
"([])" → 2. The string is balanced, but ( may not contain [, so only "[]" counts.
"([]{})" → 4 ("[]{}"). The rule-breaking { makes the ( dead, and the string still keeps the earlier "[]".
")()())" → 4. The single-kind LC 32 behavior is unchanged.
"{[}]" → 0. The closers cross.
"[(])" → 0
"{}[]()" → 6. Concatenations are valid, and so is a lower rank following a higher one.
"{{}}[[()]]" → 10. Same-rank nesting is allowed.
"(()[[]]" → 6 ("()[[]]"); the first ( dies when [ opens inside it
")){[]}(" → start 2, length 4
A single opener or closer → 0

Follow-ups

Return the substring, or every longest one. longest_valid_span already returns the leftmost one. To get every start index of maximum length, keep a list and reset it when a longer length appears. The cost stays O(n).
Configurable rules. The interviewer gives an "allowed directly inside" relation, for example "( may hold {, but [ may hold only (". Replace the rank comparison with c in ALLOWED[s[stack[-1]]]. If the relation is not transitive, checking only the direct parent is exactly the rule. The reset logic does not change.
Streaming or very large input. Process chunks with the same state, which is the stack plus best. Memory is O(depth of live openers), not O(n). Track absolute offsets so the base indices remain meaningful.
DP alternative. Let dp[i] be the longest valid substring ending at i. For a closer at i, j = i - dp[i-1] - 1 is its partner candidate. The nesting check needs to know the highest rank directly inside (j, i), so keep top_rank[i]. The stack version is simpler. Mention the DP, then stick with the stack.
Minimum deletions or count of valid substrings. For minimum deletions to make the whole string valid, the walls of the greedy stack pass give a fast heuristic. With the rank rule, a dead opener might be kept if the offending inner pair is deleted instead, so the exact answer needs an interval DP: O(n^3) time, O(n^2) space. To count valid substrings, add count[base] + 1 at each successful pop (keep count[] keyed by base index), still O(n).

Interviewer expectations

Mid-level (L4)

Explains why a single counter fails with several bracket kinds, and writes a correct full-string validator with the nesting rule.
Reaches the O(n^3) brute force, then the index-stack idea with some prompting.
Gets the basic cases right: concatenations and an unmatched closer resetting the stack.

Senior (L5)

Finds the O(n) stack on their own and handles all three events: matching closer, bad closer, and rule-breaking opener.
Explains why the innermost dead opener becomes the new base, not i - 1, using ([]{}) as the counterexample.
Tests with a randomized brute-force oracle and states the invariant.

Staff (L6+)

Says why checking only the direct parent is enough (the open chain is monotone) and how that changes under a non-transitive "allowed inside" relation.
Moves to configurable rules and streaming input without rewriting the core loop.
Compares the stack with the DP formulation, and knows which follow-ups, such as exact minimum deletions under the rank rule, stop being linear.