163. Longest Valid Parentheses Substring

Given a string containing only '(' and ')', find the length of its longest contiguous substring that is a valid (balanced) sequence of parentheses.

Input: The input is a single line containing a string of only '(' and ')' characters; the string may be empty. Output: Print a single integer - the length of the longest valid (balanced) parentheses substring.

0 <= |s| <= 10^5

This uses the SAME 'stack of indices, subtract for length' technique as 'Largest Rectangular Area in a Histogram' - both track a boundary/base position that shifts as elements get resolved, then compute a span via simple index subtraction.

Find the length of the longest contiguous substring of parentheses that is properly balanced. Brute force: Check every possible substring directly for balance - this costs O(n³) or worse (O(n²) substrings, each taking O(n) to verify), far too slow for large strings. Optimised: The stack-of-indices technique tracks exactly where the CURRENT valid sequence 'restarts from' at every point - the sentinel -1 handles the case where the very beginning of the string participates in a valid sequence, and every ')' either extends a current valid run (computed via simple subtraction) or marks a new restart point, all in a single linear pass.

Check every substring of the string for validity by simulating a stack (or counter) over its characters and confirming it fully balances, keeping track of the longest one found. This directly verifies the definition of a valid substring for every one of the O(n^2) substrings. Time: O(n^2) Space: O(n)

Scan left to right counting opens and closes, and whenever closes exceed opens reset both counters to zero (an invalid point), otherwise whenever they're equal update the answer with twice the close count; then repeat the same idea scanning right to left with roles reversed, to catch valid substrings that a left-heavy scan alone would miss (like extra unmatched opens at the very start). This achieves the same linear time as the DP approach but needs only a few integer counters instead of an auxiliary array, dropping the space to constant. Time: O(n) Space: O(1)

Maintain dp[i] representing the length of the longest valid parentheses substring ending exactly at index i, computed in one left-to-right pass: if s[i] is ')' and it matches an open bracket found either directly before it or just past the substring ending at i-1, extend dp[i] using dp[i-1] and dp[i - dp[i-1] - 2]. This computes the answer in a single pass over pre-solved smaller subproblems rather than re-verifying every substring from scratch. Time: O(n) Space: O(n)

1. Use a stack of INDICES, starting with a sentinel index of -1 pushed initially (to simplify length calculations). 2. On '(': push its index. 3. On ')': pop the top (matching it) - if the stack becomes empty after popping, push the current index as a new 'base' (this ')' couldn't be matched); otherwise, the current valid length is (current index - the new stack top's index).

Time: O(n) - one single pass through the string, with O(1) stack operations at each character. Space: O(n) in the worst case, for the stack.

An empty string (answer 0); a string with no valid pairs at all, such as all '(' or all ')'; strings up to 10^5 characters for performance.

Be ready to explain the purpose of the initial sentinel -1 clearly - without it, computing the length of a valid sequence that starts right at index 0 would require awkward special-casing instead of a clean, uniform subtraction formula.