Welcome to Subscribe On Youtube

32. Longest Valid Parentheses

Description

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

 

Example 1:

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

Example 2:

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

Example 3:

Input: s = ""
Output: 0

 

Constraints:

  • 0 <= s.length <= 3 * 104
  • s[i] is '(', or ')'.

Solutions

Solution 1: Dynamic Programming

We define $f[i]$ to be the length of the longest valid parentheses that ends with $s[i-1]$, and the answer is $max(f[i])$.

When $i \lt 2$, the length of the string is less than $2$, and there is no valid parentheses, so $f[i] = 0$.

When $i \ge 2$, we consider the length of the longest valid parentheses that ends with $s[i-1]$, that is, $f[i]$:

  • If $s[i-1]$ is a left parenthesis, then the length of the longest valid parentheses that ends with $s[i-1]$ must be $0$, so $f[i] = 0$.
  • If $s[i-1]$ is a right parenthesis, there are the following two cases:
    • If $s[i-2]$ is a left parenthesis, then the length of the longest valid parentheses that ends with $s[i-1]$ is $f[i-2] + 2$.
    • If $s[i-2]$ is a right parenthesis, then the length of the longest valid parentheses that ends with $s[i-1]$ is $f[i-1] + 2$, but we also need to consider whether $s[i-f[i-1]-2]$ is a left parenthesis. If it is a left parenthesis, then the length of the longest valid parentheses that ends with $s[i-1]$ is $f[i-1] + 2 + f[i-f[i-1]-2]$.

Therefore, we can get the state transition equation:

\[\begin{cases} f[i] = 0, & \text{if } s[i-1] = '(',\\ f[i] = f[i-2] + 2, & \text{if } s[i-1] = ')' \text{ and } s[i-2] = '(',\\ f[i] = f[i-1] + 2 + f[i-f[i-1]-2], & \text{if } s[i-1] = ')' \text{ and } s[i-2] = ')' \text{ and } s[i-f[i-1]-2] = '(',\\ \end{cases}\]

Finally, we only need to return $max(f)$.

The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the string.

Solution 2: Using Stack

  • Maintain a stack to store the indices of left parentheses. Initialize the bottom element of the stack with the value -1 to facilitate the calculation of the length of valid parentheses.
  • Iterate through each element of the string:
    • If the character is a left parenthesis, push the index of the character onto the stack.
    • If the character is a right parenthesis, pop an element from the stack to represent that we have found a valid pair of parentheses.
      • If the stack is empty, it means we couldn’t find a left parenthesis to match the right parenthesis. In this case, push the index of the character as a new starting point.
      • If the stack is not empty, calculate the length of the valid parentheses and update it.

Summary:

The key to this algorithm is to maintain a stack to store the indices of left parentheses and then update the length of the valid substring of parentheses by pushing and popping elements.

The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the string.

  • class Solution {
        public int longestValidParentheses(String s) {
            int n = s.length();
            int[] f = new int[n + 1];
            int ans = 0;
            for (int i = 2; i <= n; ++i) {
                if (s.charAt(i - 1) == ')') {
                    if (s.charAt(i - 2) == '(') {
                        f[i] = f[i - 2] + 2;
                    } else {
                        int j = i - f[i - 1] - 1;
                        if (j > 0 && s.charAt(j - 1) == '(') {
                            f[i] = f[i - 1] + 2 + f[j - 1];
                        }
                    }
                    ans = Math.max(ans, f[i]);
                }
            }
            return ans;
        }
    }
    
    //////
    
    class Solution_noExtraSpace {
        public int longestValidParentheses(String s) {
            int res = 0, left = 0, right = 0, n = s.length();
    
            // from left to right, '(()' => will never hit left==right
            for (int i = 0; i < n; ++i) {
                if (s.charAt(i) == '(') ++left;
                else ++right;
    
                if (left == right) res = Math.max(res, 2 * right);
                else if (right > left) left = right = 0;
            }
    
            // from right to left, '())' => will never hit left==right
            left = right = 0;
            for (int i = n - 1; i >= 0; --i) {
                if (s.charAt(i) == '(') ++left;
                else ++right;
    
                if (left == right) res = Math.max(res, 2 * left);
                else if (left > right) left = right = 0;
            }
            return res;
    
        }
    }
    
    //////
    
    class Solution_stack {
        public int longestValidParentheses(String s) {
            Stack<Integer> sk = new Stack<>();
            int start = 0;
            int result = 0;
            for (int i = 0;i < s.length(); i++) {
                if(s.charAt(i) == '(') {
                    sk.push(i);
                } else {
                    if (sk.empty()) {
                        start = i + 1;
                    } else {
                        sk.pop();
                        result = Math.max(result, sk.isEmpty() ? i - start + 1 : i - sk.peek());
                    }
                }
            }
            return result;
    
        }
    }
    
    
  • class Solution {
    public:
        int longestValidParentheses(string s) {
            int n = s.size();
            int f[n + 1];
            memset(f, 0, sizeof(f));
            for (int i = 2; i <= n; ++i) {
                if (s[i - 1] == ')') {
                    if (s[i - 2] == '(') {
                        f[i] = f[i - 2] + 2;
                    } else {
                        int j = i - f[i - 1] - 1;
                        if (j && s[j - 1] == '(') {
                            f[i] = f[i - 1] + 2 + f[j - 1];
                        }
                    }
                }
            }
            return *max_element(f, f + n + 1);
        }
    };
    
  • class Solution:
        def longestValidParentheses(self, s: str) -> int:
            left = right = 0
            res = 0
            for c in s: # from left to right, '(()' => will never hit left==right
                if c == '(':
                    left += 1
                else:
                    right += 1
                if left == right:
                    res = max(res, 2 * left)
                if left < right:
                    left = right = 0
    
            left = right = 0 # dont forget to reset
            for c in reversed(s): # from right to left, '())' => will never hit left==right
                if c == '(':
                    left += 1
                else:
                    right += 1
                if left == right:
                    res = max(res, 2 * left)
                if left > right: # reverse '<' to '>'
                    left = right = 0
    
            return res
    
    ######
    
    class Solution:
        def longestValidParentheses(self, s: str) -> int:
            n = len(s)
            if n < 2:
                return 0
            dp = [0] * n
            for i in range(1, n):
                if s[i] == ')':
                    if s[i - 1] == '(':
                        dp[i] = 2 + (dp[i - 2] if i > 1 else 0)
                    else:
                        j = i - dp[i - 1] - 1
                        if j >= 0 and s[j] == '(':
                            dp[i] = 2 + dp[i - 1] + dp[j - 1]
            return max(dp)
    
    ######
    
    '''
    >>> s="abcdefg"
    >>> [print(i,",",c) for i, c in enumerate(s, 1)]
    1 , a
    2 , b
    3 , c
    4 , d
    5 , e
    6 , f
    7 , g
    [None, None, None, None, None, None, None]
    >>>
    '''
    class Solution:
        def longestValidParentheses(self, s: str) -> int:
            n = len(s)
            f = [0] * (n + 1)
            for i, c in enumerate(s, 1): # starting i from 1, not 0
                if c == ")":
                    if i > 1 and s[i - 2] == "(":
                        f[i] = f[i - 2] + 2
                    else:
                        j = i - f[i - 1] - 1
                        if j and s[j - 1] == "(":
                            f[i] = f[i - 1] + 2 + f[j - 1]
            return max(f)
    
    
  • func longestValidParentheses(s string) int {
    	n := len(s)
    	f := make([]int, n+1)
    	for i := 2; i <= n; i++ {
    		if s[i-1] == ')' {
    			if s[i-2] == '(' {
    				f[i] = f[i-2] + 2
    			} else if j := i - f[i-1] - 1; j > 0 && s[j-1] == '(' {
    				f[i] = f[i-1] + 2 + f[j-1]
    			}
    		}
    	}
    	return slices.Max(f)
    }
    
  • function longestValidParentheses(s: string): number {
        const n = s.length;
        const f: number[] = new Array(n + 1).fill(0);
        for (let i = 2; i <= n; ++i) {
            if (s[i - 1] === ')') {
                if (s[i - 2] === '(') {
                    f[i] = f[i - 2] + 2;
                } else {
                    const j = i - f[i - 1] - 1;
                    if (j && s[j - 1] === '(') {
                        f[i] = f[i - 1] + 2 + f[j - 1];
                    }
                }
            }
        }
        return Math.max(...f);
    }
    
    
  • /**
     * @param {string} s
     * @return {number}
     */
    var longestValidParentheses = function (s) {
        const n = s.length;
        const f = new Array(n + 1).fill(0);
        for (let i = 2; i <= n; ++i) {
            if (s[i - 1] === ')') {
                if (s[i - 2] === '(') {
                    f[i] = f[i - 2] + 2;
                } else {
                    const j = i - f[i - 1] - 1;
                    if (j && s[j - 1] === '(') {
                        f[i] = f[i - 1] + 2 + f[j - 1];
                    }
                }
            }
        }
        return Math.max(...f);
    };
    
    
  • public class Solution {
        public int LongestValidParentheses(string s) {
            int n = s.Length;
            int[] f = new int[n + 1];
            int ans = 0;
            for (int i = 2; i <= n; ++i) {
                if (s[i - 1] == ')') {
                    if (s[i - 2] == '(') {
                        f[i] = f[i - 2] + 2;
                    } else {
                        int j = i - f[i - 1] - 1;
                        if (j > 0 && s[j - 1] == '(') {
                            f[i] = f[i - 1] + 2 + f[j - 1];
                        }
                    }
                    ans = Math.Max(ans, f[i]);
                }
            }
            return ans;
        }
    }
    
  • impl Solution {
        pub fn longest_valid_parentheses(s: String) -> i32 {
            let mut ans = 0;
            let mut f = vec![0; s.len() + 1];
            for i in 2..=s.len() {
                if
                    s
                        .chars()
                        .nth(i - 1)
                        .unwrap() == ')'
                {
                    if
                        s
                            .chars()
                            .nth(i - 2)
                            .unwrap() == '('
                    {
                        f[i] = f[i - 2] + 2;
                    } else if
                        (i as i32) - f[i - 1] - 1 > 0 &&
                        s
                            .chars()
                            .nth(i - (f[i - 1] as usize) - 2)
                            .unwrap() == '('
                    {
                        f[i] = f[i - 1] + 2 + f[i - (f[i - 1] as usize) - 2];
                    }
                    ans = ans.max(f[i]);
                }
            }
            ans
        }
    }
    
    

All Problems

All Solutions