A string s is made only of the six characters ( ) [ ] { }. The three bracket kinds have a rank: round () is rank 0, square [] is rank 1, curly {} is rank 2.
A string is valid when:
- it is balanced and correctly matched, as usual (every closer closes the most recent unclosed opener of the same kind), and
- a pair of brackets only ever directly contains pairs of the same or a lower rank. So round brackets may hold only round brackets, square brackets may hold square or round ones, and curly brackets may hold anything.
The empty string is valid, and so is any concatenation of valid strings ("()[]{}", "(){()}").
Implement:
def longest_valid(s: str) -> int
Return the length of the longest contiguous substring of s that is valid (0 if there is none).
longest_valid(")[()]{[]}(") # 8 "[()]{[]}"
longest_valid("([()])") # 4 "[()]"; the outer ( ) may not hold square brackets
longest_valid("{[(])}") # 0 crossed pairs are never valid
longest_valid("[[]]((") # 4
longest_valid("") # 0
Constraints: len(s) up to 200,000, and nesting can be as deep as half of that. Aim for O(n); trying every start position is far too slow.
Show hint
for each index i, find the longest valid substring that ends at i: a closer at i can only match the opener just before the valid block ending at i - 1. For that block, also remember the highest rank among its outermost pairs so the rank rule is an O(1) check. (A stack of indices works too, if you'd rather track matches that way.)