Problem

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example

Example 1:

1
2
3

Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2:

1
2
3

Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Example 3:

1
2

Input: s = ""
Output: 0

Solution

This problem is similar with Valid Parentheses, which can be solved by using a stack.

Method 1 – Stack-Based Linear Scan

Intuition

We can use a stack to keep track of the indices of opening parentheses. When we encounter a closing parenthesis, we check if there is a matching opening parenthesis on the stack. If so, we pop it and calculate the length of the valid substring. If not, we update the starting point for the next possible valid substring. This approach helps us efficiently find the longest well-formed parentheses substring.

Approach

  1. Initialize a stack to store indices of ‘(’ characters.
  2. Set a variable start to -1 to mark the start of a potential valid substring.
  3. Iterate through the string:
    • If the character is ‘(’, push its index onto the stack.
    • If the character is ‘)’:
      • If the stack is empty, set start to the current index (no matching ‘(’).
      • If the stack is not empty, pop the top index:
        • If the stack is now empty, the valid substring starts after start.
        • If the stack is not empty, the valid substring starts after the index at the top of the stack.
  4. Track the maximum length found during the scan.
  5. Return the maximum length.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

int longestValidParentheses(const std::string& s) {
	std::stack<int> stack;
	int maxLen = 0;
	int start = -1; // Start of the current valid substring
	for (int i = 0; i < s.size(); ++i) {
		char c = s[i];
		if (c == '(') {
			stack.push(i);
		} else {
			if (stack.empty()) {
				start = i;
			} else {
				stack.pop();
				if (stack.empty()) {
					maxLen = std::max(maxLen, i - start);
				} else {
					maxLen = std::max(maxLen, i - stack.top());
				}
			}
		}
	}
	return maxLen;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

func longestValidParentheses(s string) int {
	stack := []int{}
	maxLen := 0
	start := -1 // Start of the current valid substring
	for i, c := range s {
		if c == '(' {
			stack = append(stack, i)
		} else {
			if len(stack) == 0 {
				start = i // Unmatched ')', update start
			} else {
				stack = stack[:len(stack)-1] // Found a matching '('
				if len(stack) == 0 {
					maxLen = max(maxLen, i-start)
				} else {
					maxLen = max(maxLen, i-stack[len(stack)-1])
				}
			}
		}
	}
	return maxLen
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public int longestValidParentheses(String s) {
	Stack<Integer> stack = new Stack<>();
	int maxLen = 0;
	int start = -1; // Start of the current valid substring

	for (int i = 0; i < s.length(); i++) {
		char c = s.charAt(i);
		if (c == '(') {
			stack.push(i);
		} else {
			// Unmatched ')', update start
			if (stack.empty()) {
				start = i;
			} else {
				stack.pop(); // Found a matching '('
				if (stack.empty()) {
					// All open parens matched, valid substring from start+1
					maxLen = Math.max(maxLen, i - start);
				} else {
					// There are still unmatched '(', valid substring after last unmatched '('
					maxLen = Math.max(maxLen, i - stack.peek());
				}
			}
		}
	}
	return maxLen;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

fun longestValidParentheses(s: String): Int {
	val stack = ArrayDeque<Int>()
	var maxLen = 0
	var start = -1 // Start of the current valid substring
	for (i in s.indices) {
		val c = s[i]
		if (c == '(') {
			stack.addLast(i)
		} else {
			if (stack.isEmpty()) {
				start = i // Unmatched ')', update start
			} else {
				stack.removeLast() // Found a matching '('
				if (stack.isEmpty()) {
					maxLen = maxOf(maxLen, i - start)
				} else {
					maxLen = maxOf(maxLen, i - stack.last())
				}
			}
		}
	}
	return maxLen
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def longestValidParentheses(s: str) -> int:
	stack = []
	max_len = 0
	start = -1  # Start of the current valid substring
	for i, c in enumerate(s):
		if c == '(':  # Push index of '('
			stack.append(i)
		else:
			if not stack:
				start = i  # Unmatched ')', update start
			else:
				stack.pop()  # Found a matching '('
				if not stack:
					max_len = max(max_len, i - start)
				else:
					max_len = max(max_len, i - stack[-1])
	return max_len
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

pub fn longest_valid_parentheses(s: &str) -> i32 {
	let mut stack = Vec::new();
	let mut max_len = 0;
	let mut start = -1; // Start of the current valid substring
	for (i, c) in s.chars().enumerate() {
		if c == '(' {
			stack.push(i as i32);
		} else {
			if stack.is_empty() {
				start = i as i32; // Unmatched ')', update start
			} else {
				stack.pop(); // Found a matching '('
				if stack.is_empty() {
					max_len = max_len.max(i as i32 - start);
				} else {
					max_len = max_len.max(i as i32 - *stack.last().unwrap());
				}
			}
		}
	}
	max_len
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

function longestValidParentheses(s: string): number {
	const stack: number[] = [];
	let maxLen = 0;
	let start = -1; // Start of the current valid substring
	for (let i = 0; i < s.length; i++) {
		const c = s[i];
		if (c === '(') {
			stack.push(i);
		} else {
			if (stack.length === 0) {
				start = i; // Unmatched ')', update start
			} else {
				stack.pop(); // Found a matching '('
				if (stack.length === 0) {
					maxLen = Math.max(maxLen, i - start);
				} else {
					maxLen = Math.max(maxLen, i - stack[stack.length - 1]);
				}
			}
		}
	}
	return maxLen;
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string. Each character is processed once.
  • 🧺 Space complexity: O(n), for the stack used to store indices of ‘(’.

Method 2 – Two-Pass Linear Scan (O(1) Space)

Intuition

We can solve this problem without using a stack by counting the number of opening and closing parentheses as we scan the string. By making two passes—one from left to right and another from right to left—we can handle both cases where there are extra closing or opening parentheses. This approach allows us to find the longest valid substring using only a few variables.

Approach

  1. Initialize counters for open and close parentheses and a variable for the maximum length.
  2. Scan the string from left to right:
    • Increment the open counter for ‘(’.
    • Increment the close counter for ‘)’.
    • If open equals close, update the maximum length.
    • If close exceeds open, reset both counters to zero.
  3. Scan the string from right to left:
    • Increment the open counter for ‘(’.
    • Increment the close counter for ‘)’.
    • If open equals close, update the maximum length.
    • If open exceeds close, reset both counters to zero.
  4. Return the maximum length found in both passes.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

int longestValidParentheses(const std::string& s) {
	int maxLen = 0, open = 0, close = 0, n = s.size();
	// Left to right
	for (int i = 0; i < n; ++i) {
		if (s[i] == '(') open++;
		else close++;
		if (open == close) maxLen = std::max(maxLen, 2 * close);
		else if (close > open) open = close = 0;
	}
	open = close = 0;
	// Right to left
	for (int i = n - 1; i >= 0; --i) {
		if (s[i] == '(') open++;
		else close++;
		if (open == close) maxLen = std::max(maxLen, 2 * open);
		else if (open > close) open = close = 0;
	}
	return maxLen;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

func longestValidParentheses(s string) int {
	maxLen, open, close := 0, 0, 0
	n := len(s)
	// Left to right
	for i := 0; i < n; i++ {
		if s[i] == '(' {
			open++
		} else {
			close++
		}
		if open == close {
			if 2*close > maxLen {
				maxLen = 2 * close
			}
		} else if close > open {
			open, close = 0, 0
		}
	}
	open, close = 0, 0
	// Right to left
	for i := n - 1; i >= 0; i-- {
		if s[i] == '(' {
			open++
		} else {
			close++
		}
		if open == close {
			if 2*open > maxLen {
				maxLen = 2 * open
			}
		} else if open > close {
			open, close = 0, 0
		}
	}
	return maxLen
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

public int longestValidParentheses(String s) {
	int maxLen = 0, open = 0, close = 0, n = s.length();
	// Left to right
	for (int i = 0; i < n; i++) {
		if (s.charAt(i) == '(') open++;
		else close++;
		if (open == close) maxLen = Math.max(maxLen, 2 * close);
		else if (close > open) open = close = 0;
	}
	open = close = 0;
	// Right to left
	for (int i = n - 1; i >= 0; i--) {
		if (s.charAt(i) == '(') open++;
		else close++;
		if (open == close) maxLen = Math.max(maxLen, 2 * open);
		else if (open > close) open = close = 0;
	}
	return maxLen;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

fun longestValidParentheses(s: String): Int {
	var maxLen = 0
	var open = 0
	var close = 0
	val n = s.length
	// Left to right
	for (i in 0 until n) {
		if (s[i] == '(') open++
		else close++
		if (open == close) maxLen = maxOf(maxLen, 2 * close)
		else if (close > open) { open = 0; close = 0 }
	}
	open = 0; close = 0
	// Right to left
	for (i in n - 1 downTo 0) {
		if (s[i] == '(') open++
		else close++
		if (open == close) maxLen = maxOf(maxLen, 2 * open)
		else if (open > close) { open = 0; close = 0 }
	}
	return maxLen
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def longestValidParentheses(s: str) -> int:
	max_len = open = close = 0
	n = len(s)
	# Left to right
	for i in range(n):
		if s[i] == '(': open += 1
		else: close += 1
		if open == close:
			max_len = max(max_len, 2 * close)
		elif close > open:
			open = close = 0
	open = close = 0
	# Right to left
	for i in range(n - 1, -1, -1):
		if s[i] == '(': open += 1
		else: close += 1
		if open == close:
			max_len = max(max_len, 2 * open)
		elif open > close:
			open = close = 0
	return max_len
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

pub fn longest_valid_parentheses(s: &str) -> i32 {
	let n = s.len();
	let bytes = s.as_bytes();
	let mut max_len = 0;
	let (mut open, mut close) = (0, 0);
	// Left to right
	for i in 0..n {
		if bytes[i] == b'(' { open += 1; } else { close += 1; }
		if open == close {
			max_len = max_len.max(2 * close);
		} else if close > open {
			open = 0; close = 0;
		}
	}
	open = 0; close = 0;
	// Right to left
	for i in (0..n).rev() {
		if bytes[i] == b'(' { open += 1; } else { close += 1; }
		if open == close {
			max_len = max_len.max(2 * open);
		} else if open > close {
			open = 0; close = 0;
		}
	}
	max_len as i32
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

function longestValidParentheses(s: string): number {
	let maxLen = 0, open = 0, close = 0, n = s.length;
	// Left to right
	for (let i = 0; i < n; i++) {
		if (s[i] === '(') open++;
		else close++;
		if (open === close) maxLen = Math.max(maxLen, 2 * close);
		else if (close > open) open = close = 0;
	}
	open = close = 0;
	// Right to left
	for (let i = n - 1; i >= 0; i--) {
		if (s[i] === '(') open++;
		else close++;
		if (open === close) maxLen = Math.max(maxLen, 2 * open);
		else if (open > close) open = close = 0;
	}
	return maxLen;
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string. Each character is processed twice (once in each direction).
  • 🧺 Space complexity: O(1), as only a few integer variables are used.

Method 3 – Dynamic Programming

Intuition

We can use dynamic programming to keep track of the length of the longest valid parentheses substring ending at each position. By building up a DP array, we can efficiently compute the answer by considering previous results and extending them when we find matching pairs.

Approach

  1. Create a DP array of the same length as the string, initialized to 0.
  2. Iterate through the string from left to right.
  3. For each closing parenthesis at index i, check if there is a matching opening parenthesis:
    • If the character before is ‘(’, set dp[i] = dp[i-2] + 2 (if i >= 2).
    • If the character before is ‘)’ and the character at i - dp[i-1] - 1 is ‘(’, set dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2] (if valid).
  4. Track the maximum value in the DP array as the answer.
  5. Return the maximum length found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

int longestValidParentheses(const std::string& s) {
	int n = s.size(), result = 0;
	std::vector<int> dp(n, 0);
	for (int i = 1; i < n; ++i) {
		if (s[i] == ')') {
			if (s[i-1] == '(') {
				dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
			} else if (i - dp[i-1] - 1 >= 0 && s[i - dp[i-1] - 1] == '(') {
				dp[i] = dp[i-1] + 2 + (i - dp[i-1] - 2 >= 0 ? dp[i - dp[i-1] - 2] : 0);
			}
			result = std::max(result, dp[i]);
		}
	}
	return result;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

func longestValidParentheses(s string) int {
	n := len(s)
	dp := make([]int, n)
	result := 0
	for i := 1; i < n; i++ {
		if s[i] == ')' {
			if s[i-1] == '(' {
				if i >= 2 {
					dp[i] = dp[i-2] + 2
				} else {
					dp[i] = 2
				}
			} else if i-dp[i-1]-1 >= 0 && s[i-dp[i-1]-1] == '(' {
				if i-dp[i-1]-2 >= 0 {
					dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]
				} else {
					dp[i] = dp[i-1] + 2
				}
			}
			if dp[i] > result {
				result = dp[i]
			}
		}
	}
	return result
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public int longestValidParentheses(String s) {
	int[] dp = new int[s.length()];
	int result = 0;
	for (int i = 1; i < s.length(); i++) {
		if (s.charAt(i) == ')') {
			if (s.charAt(i-1) == '(') {
				dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
			} else if (i - dp[i-1] - 1 >= 0 && s.charAt(i - dp[i-1] - 1) == '(') {
				dp[i] = dp[i-1] + 2 + (i - dp[i-1] - 2 >= 0 ? dp[i - dp[i-1] - 2] : 0);
			}
			result = Math.max(result, dp[i]);
		}
	}
	return result;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

fun longestValidParentheses(s: String): Int {
	val n = s.length
	val dp = IntArray(n)
	var result = 0
	for (i in 1 until n) {
		if (s[i] == ')') {
			if (s[i-1] == '(') {
				dp[i] = (if (i >= 2) dp[i-2] else 0) + 2
			} else if (i - dp[i-1] - 1 >= 0 && s[i - dp[i-1] - 1] == '(') {
				dp[i] = dp[i-1] + 2 + if (i - dp[i-1] - 2 >= 0) dp[i - dp[i-1] - 2] else 0
			}
			result = maxOf(result, dp[i])
		}
	}
	return result
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def longestValidParentheses(s: str) -> int:
	n = len(s)
	dp = [0] * n
	result = 0
	for i in range(1, n):
		if s[i] == ')':
			if s[i-1] == '(': 
				dp[i] = (dp[i-2] if i >= 2 else 0) + 2
			elif i - dp[i-1] - 1 >= 0 and s[i - dp[i-1] - 1] == '(': 
				dp[i] = dp[i-1] + 2 + (dp[i - dp[i-1] - 2] if i - dp[i-1] - 2 >= 0 else 0)
			result = max(result, dp[i])
	return result
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

pub fn longest_valid_parentheses(s: &str) -> i32 {
	let n = s.len();
	let bytes = s.as_bytes();
	let mut dp = vec![0; n];
	let mut result = 0;
	for i in 1..n {
		if bytes[i] == b')' {
			if bytes[i-1] == b'(' {
				dp[i] = if i >= 2 { dp[i-2] } else { 0 } + 2;
			} else if i as i32 - dp[i-1] as i32 - 1 >= 0 && bytes[i - dp[i-1] - 1] == b'(' {
				dp[i] = dp[i-1] + 2 + if i - dp[i-1] - 2 < n { dp[i - dp[i-1] - 2] } else { 0 };
			}
			result = result.max(dp[i]);
		}
	}
	result as i32
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

function longestValidParentheses(s: string): number {
	const n = s.length;
	const dp = new Array(n).fill(0);
	let result = 0;
	for (let i = 1; i < n; i++) {
		if (s[i] === ')') {
			if (s[i-1] === '(') {
				dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
			} else if (i - dp[i-1] - 1 >= 0 && s[i - dp[i-1] - 1] === '(') {
				dp[i] = dp[i-1] + 2 + (i - dp[i-1] - 2 >= 0 ? dp[i - dp[i-1] - 2] : 0);
			}
			result = Math.max(result, dp[i]);
		}
	}
	return result;
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string. Each character is processed once.
  • 🧺 Space complexity: O(n), for the DP array used to store results at each position.

Dry Run

Let’s dry run the DP approach on the example s = ")()())":

i : [0, 1, 2, 3, 4, 5] s : [), (, ), (, ), )] DP : [0, 0, 2, 0, 2, 4]

Step-by-step:

  • i = 0: s[0] = ‘)’, cannot end a valid substring, DP[0] = 0
  • i = 1: s[1] = ‘(’, cannot end a valid substring, DP[1] = 0
  • i = 2: s[2] = ‘)’, s[1] = ‘(’, so DP[2] = DP[0] + 2 = 2
  • i = 3: s[3] = ‘(’, cannot end a valid substring, DP[3] = 0
  • i = 4: s[4] = ‘)’, s[3] = ‘(’, so DP[4] = DP[2] + 2 = 2
  • i = 5: s[5] = ‘)’, s[4] = ‘)’, look for matching ‘(’: i - DP[4] - 1 = 1, s[1] = ‘(’, so DP[5] = DP[4] + 2 + DP[0] = 2 + 2 + 0 = 4

The maximum value in DP is 4, which is the length of the longest valid parentheses substring.