Show problems as
Classic problem #32HardStringDynamic ProgrammingStackBracket Sequences

Longest Valid Parentheses

Real-world version: Longest Clean Trace Window
Tracked in this browser only
Read Longest Valid Parentheses on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A profiler writes one character into trace per event it sees: ( when a span opens and ) when a span closes. No other character is written, and a run with no events at all leaves trace empty.

A window is a stretch of neighbouring characters of trace. A window is clean when its opens and closes pair off completely inside it: every ) in the window is answered by an unused ( sitting earlier in the same window, and no ( in the window is left waiting when the window ends.

Return the length of the longest clean window. When no window of one character or more is clean, return 0.

Examples

Example 1

Input
trace = "))(())()"
Output
6

Dropping the two stray closes at the front leaves the last six characters, which pair off completely.

Example 2

Input
trace = "()(()"
Output
2

The first two characters pair off, and so do the last two, but no clean window reaches past the open at position 2.

Example 3

Input
trace = "(("
Output
0

Both spans are still waiting when the trace ends, so nothing pairs off.

Constraints

  • 0 <= trace.length <= 3 * 10^4
  • Every character of trace is either '(' or ')'

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def longest_clean_window(trace: str) -> int:
Java
public int longestCleanWindow(String trace)

More on the same topics