hard

Longest Valid Parentheses

Find the length of the longest substring of well-formed parentheses.

1. Define the problem

Longest Valid Parentheses

You are given a string containing only the characters ( and ). Find the length of the longest run of characters, sitting side by side, that is properly balanced. Properly balanced means every opening bracket has a matching closing bracket after it, and the brackets never close before they open. Only a closing bracket can finish a valid run, so keep, for every position, the length of the valid run ending exactly there . A closing bracket either sits right after an opening one, or it closes a bracket that sits just before a run already counted — in which case the run before that one gets glued on as well.

Constraints

  • 0 ≤ s.length ≤ 30000
  • s contains only the characters ( and )
  • The answer is a length, not the substring itself

Example

Inputs = ")()())"
Output4

Explanation The longest balanced run is "()()" , which sits at positions 1 to 4.

2. Know the words first

In plain terms

Balanced
Every ( has a matching ) after it and nothing closes out of order. "(())" is balanced; ")(" is not.
Substring
A run of characters that sit next to each other in the original string. You cannot skip characters in the middle.
Run ending here
The length of the longest balanced substring whose last character is this one. It is 0 when this position cannot end a balanced run.
3. Visualize the solution

Length of the balanced run ending at each position of ")()())"

Length of the balanced run ending at each position of ")()())"
Statusinit

Every position starts at 0 and the best length so far is 0.

What happens in this step

s = ")()())"
lengths = 0, 0, 0, 0, 0, 0
best = 0

Position 0 is left alone: a run cannot end at the first character, because there is nothing before it to open the bracket.
Step 1 of 5

Steps to visualize

  1. The row is the 6 characters of ")()())"; the label shows the position and the character.
  2. Each cell holds the length of the longest balanced run that ends exactly at that character.
  3. An opening bracket can never end a balanced run, so those cells stay 0.
  4. A ) sitting right after a ( scores 2, plus whatever run ended just before the pair.
  5. A ) sitting after another ) looks back past that run for a matching ( and glues everything together.
  6. The box marks the run being measured.
  7. The answer is the largest number in the row.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Length of the balanced run ending at each position of ")()())"
Statusinit

Every position starts at 0 and the best length so far is 0.

What happens in this step

s = ")()())"
lengths = 0, 0, 0, 0, 0, 0
best = 0

Position 0 is left alone: a run cannot end at the first character, because there is nothing before it to open the bracket.
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function longestValidParentheses(s) {
  const lengths = new Array(s.length).fill(0);
  let best = 0;

  for (let i = 1; i < s.length; i += 1) {
    if (s[i] !== ')') {
      continue;
    }

    if (s[i - 1] === '(') {
      lengths[i] = (i >= 2 ? lengths[i - 2] : 0) + 2;
    } else {
      const start = i - lengths[i - 1] - 1;
      if (start >= 0 && s[start] === '(') {
        lengths[i] = lengths[i - 1] + 2 + (start >= 1 ? lengths[start - 1] : 0);
      }
    }

    if (lengths[i] > best) {
      best = lengths[i];
    }
  }

  return best;
}
Time
O(n)
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
s = ")()())"4example from the description
s = "(()"2a leftover opening bracket at the front
s = ""0empty string
s = ")("0brackets in the wrong order, so nothing is balanced
s = "()(())"6a nested run glued onto the run before it
s = "()(()"2a valid run followed by brackets that never close

Keep reading