Stack

Longest Valid Parentheses

hard

DESCRIPTION (inspired by Leetcode.com)

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. A well-formed parentheses string is one that follows these rules:

Open brackets must be closed by a matching pair in the correct order.

For example, given the string "(()", the longest valid parentheses substring is "()", which has a length of 2. Another example is the string ")()())", where the longest valid parentheses substring is "()()", which has a length of 4.

Example 1:
Inputs:

s = "())))"

Output:

(Explanation: The longest valid parentheses substring is "()")

Example 2:
Inputs:

s = "((()()())"

Output:

(Explanation: The longest valid parentheses substring is "(()()())" with a length of 8)

Example 3:
Inputs:

s = ""

Output:

Code Editor

Java

public class Solution {
    public Integer longest_valid_parentheses(String s) {
        // Your code goes here
    }
}

Run your code to see results here

Have suggestions or found something wrong?

Explanation

At a high level, we can solve this problem by iterating over each index of the string, and then calculating the length of the longest valid parentheses substring that ends at that index. We can then take the maximum of these lengths to get the final answer.

Each time we encounter a closing parenthesis ')', it has the potential to close a valid parentheses substring. In order to calculate the length of the longest valid parentheses substring that ends at a given index, we need to know the index of the last unmatched opening parenthesis '('.

The length of the valid substring ending at the current index can be calculated by taking the difference between the current index and the index of the last unmatched opening parenthesis.

Let's visualize a few examples to understand how that calculation works:

Current index: 2. Last unmatched opening parenthesis at index 0. Length: 2 - 0 = 2

Current index: 3. Last unmatched opening parenthesis at index 1. Length: 3 - 1 = 2

Current index: 5. Last unmatched opening parentheses = 1. Length = 5 - 1 = 4.

If there aren't any unmatched opening parentheses remaining after using the current closing parentheses, then we need to know the "start" of the current valid substring. Setting this value to -1 makes our calculation easier, as we can simply take the difference between the current index and the start of the valid substring to get the length.

Current index: 3. The start of the current valid substring is -1, so length = 3 - (-1) = 4

However, if the closing parenthesis ')' doesn't close any valid substring (as shown below), then we can simply ignore it, and set the start of the current valid substring to the current index.

Current index: 3. But there is no unmatched opening parenthesis. Length: 0

This leads us to the following algorithm:

Initialize a stack. The stack will always contain the index of the last unmatched opening parenthesis, or the "start" of the current valid substring. Initially, the stack will contain -1 as the start of the current valid substring.
Each time we encounter an opening parenthesis '(', we'll push its index onto the stack, which represents the index of the last unmatched opening parenthesis.
Each time we encounter a closing parenthesis ')', we'll do the following:
1. We first pop the top element from the stack, as this closing parenthesis has the potential to close a valid parentheses substring.
2. Now, after popping, there are two possible cases:
  1. The stack is not empty, and the top of the stack represents the index of the last unmatched opening parenthesis. We calculate the length of the valid substring ending at the current index by taking the difference between the current index and the index of the last unmatched opening parenthesis.
  2. The stack is empty. This means that this closing parenthesis was unmatched. We'll update the start of the valid substring to the current index by pushing the current index onto the stack.

Solution

Visualization

Java

Try these examples:


public int longestValidParentheses(String s) {
    int maxLen = 0;
    Stack<Integer> stack = new Stack<>();
    stack.push(-1);
    
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(') {
            stack.push(i);
        } else {
            stack.pop();
            if (stack.isEmpty()) {
                stack.push(i);
            } else {
                maxLen = Math.max(maxLen, i - stack.peek());
            }
        }
    }
    
    return maxLen;
}

longest valid parentheses

0 / 17

Solution Visualization

Visualization

Java

Try these examples:


public int longestValidParentheses(String s) {
    int maxLen = 0;
    Stack<Integer> stack = new Stack<>();
    stack.push(-1);
    
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(') {
            stack.push(i);
        } else {
            stack.pop();
            if (stack.isEmpty()) {
                stack.push(i);
            } else {
                maxLen = Math.max(maxLen, i - stack.peek());
            }
        }
    }
    
    return maxLen;
}

longest valid parentheses

0 / 17

Walkthrough

Example 1: s = "(()())"

Initialization

We initialize our stack with [-1] as a sentinel value representing the start of the current valid substring, and set max_len = 0.

Visualization

longest valid parentheses

0 / 0

Stack initialized with [-1], max_len = 0

Push opening parentheses at indices 0 and 1

We encounter '(' at indices 0 and 1. For each, we push the index onto the stack. The stack now holds [-1, 0, 1] — both indices are waiting to be matched.

Visualization

checking character '(' at index 0

0 / 2

Push indices 0 and 1 onto the stack

First match at index 2

We hit ')' at index 2. Pop index 1 from the stack — it's been matched. The top of the stack is now 0 (the last unmatched '('), so the valid substring length is 2 - 0 = 2. Update max_len = 2.

Visualization

checking character ')' at index 2

0 / 1

Pop index 1, calculate length: 2 - 0 = 2

Push at index 3, then match at index 4

Index 3 is '(' — push it. Index 4 is ')' — pop index 3. The top of the stack is still 0, so the valid substring length is 4 - 0 = 4. Update max_len = 4.

Visualization

checking character '(' at index 3

0 / 3

Push index 3, pop it at index 4. Length: 4 - 0 = 4

Final match at index 5

The last ')' at index 5 pops index 0. Now the top of the stack is -1 (our sentinel). The valid substring length is 5 - (-1) = 6 — the entire string is valid. Update max_len = 6.

Visualization

checking character ')' at index 5

0 / 1

Pop index 0, calculate length: 5 - (-1) = 6

We return max_len = 6.

Example 2: s = ")())()()"

Unmatched ) at index 0

After initializing the stack with [-1], we immediately hit ')'. We pop -1, but now the stack is empty — this means the ) was unmatched. We push index 0 onto the stack as the new "start" marker.

Visualization

longest valid parentheses

0 / 3

Pop -1, stack empty → push index 0 as new start

Match () at indices 1–2

Push '(' at index 1. Then ')' at index 2 pops it. Top of stack is 0, so valid length is 2 - 0 = 2. Update max_len = 2.

Visualization

checking character '(' at index 1

0 / 3

Push index 1, pop at index 2. Length: 2 - 0 = 2

Another unmatched ) at index 3

We hit ')' at index 3 and pop index 0. The stack is empty again — another unmatched ). Push index 3 as the new start marker. This resets where the next valid substring can begin.

Visualization

checking character ')' at index 3

0 / 1

Pop index 0, stack empty → push index 3 as new start

Process ()() from indices 4–7

From index 4 onward, we process two consecutive pairs. Push 4, match at 5 (length 5 - 3 = 2). Push 6, match at 7 (length 7 - 3 = 4). Because both pairs are adjacent and share the same base marker at index 3, the length keeps growing. Update max_len = 4.

Visualization

checking character '(' at index 4

0 / 8

Two consecutive matches extend from the same start. Length: 7 - 3 = 4

We return max_len = 4.

What is the time complexity of this solution?

O(n)

O(n³)

O(2ⁿ)

O(n * logn)

Checking progress…

Stack

Longest Valid Parentheses

hard

DESCRIPTION (inspired by Leetcode.com)

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. A well-formed parentheses string is one that follows these rules:

Open brackets must be closed by a matching pair in the correct order.

Example 1:
Inputs:

s = "())))"

Output:

(Explanation: The longest valid parentheses substring is "()")

Example 2:
Inputs:

s = "((()()())"

Output:

(Explanation: The longest valid parentheses substring is "(()()())" with a length of 8)

Example 3:
Inputs:

s = ""

Output:

Code Editor

Java

public class Solution {
    public Integer longest_valid_parentheses(String s) {
        // Your code goes here
    }
}