Open in app

Sign in

Write

Sign in

Longest Valid Parentheses — LeetCode

Problem statement

Alkesh Ghorpade
Nerd For Tech
8 min readMay 28, 2023

--

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

Problem statement taken from: https://leetcode.com/problems/longest-valid-parentheses

Example 1:

Example 2:

Example 3:

Constraints:

Solutions for Longest Valid Parentheses

Approach 1: Brute Force

The brute force approach is to generate all the substrings and check whether every string is valid parentheses. If the substring is valid and the length exceeds the maximum length seen so far, then update the maximum length. We return this maximum length as the longest valid parentheses.

The problem with this approach is the time complexity which is O(n³). Three nested for loops will be used. The first two will generate all the substrings, and the third inner loop will verify whether the substring is valid parentheses.

Approach 2: Using Stack

An efficient way to solve the longest valid parentheses is using a Stack. The solution is similar to our approach in valid parentheses problem. Instead of pushing the open brackets ( to the stack, we push the indexes of the opening brackets.

The algorithm for this approach is as follows:

A C++ snippet of this algorithm is as below:

int longestValidParentheses(string s) {
    stack<int> stk;
    stk.push(-1);

    int result = 0;

    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '(') {
            stk.push(i);
        } else {
            if (!stk.empty()) {
                stk.pop();
            }

            if (!stk.empty()) {
                result = max(result, i - stk.top());
            } else {
                stk.push(i);
            }
        }
    }

    return result;
}

The time complexity of this approach is O(n) because we are iterating over the string once. The space complexity is also O(n), as we used an additional data structure, Stack.

Approach 3: Using left and right counters

Using two counters, we can solve this problem in O(1) time.

  • The idea is to scan the string from left to right.
  • We keep track of the number of open and closed braces using left and right counters. We increment the left and right counter by 1 when identifying an opening ( and closing ) braces.
  • When the left and right counters are equal, the length of the current substring is calculated. If it exceeds the previous longest valid parentheses, we update the result with the current substring length.
  • At any point while scanning, if the right counter value exceeds the left counter, the substring is not a valid parentheses string. We set the left and right counters to 0.
  • We then scan the string from right to left and repeat similar steps above.

Let’s check the algorithm for this approach.

Algorithm

The time complexity of the above approach is O(n), and the space complexity is O(1).

Check out our solutions in C++, Golang, and Javascript.

C++ solution

class Solution {
public:
    // Main function to return the length of
    // the longest valid parentheses
    int longestValidParentheses(string s) {
        int left = 0, right = 0, maxLength = 0;
        int n = s.length();

        // iterate the string from left to right
        for(int i = 0; i < n; i++) {
            if(s[i] == '(') {
                left++;
            } else {
                right++;
            }

            // if left is equal to right, we found a
            // valid parentheses substring
            if(left == right) {
                maxLength = max(maxLength, 2 * right);
            } else if (right > left) {
                // reset the left and right counter when we have
                // invalid parentheses substring
                left = 0;
                right = 0;
            }
        }

        left = 0;
        right = 0;

        // iterate the string from right to left
        for(int i = n - 1; i >= 0; i--) {
            if(s[i] == '(') {
                left++;
            } else {
                right++;
            }

            // if left is equal to right, we found a
            // valid parentheses substring
            if(left == right) {
                maxLength = max(maxLength, 2 * right);
            } else if (left > right) {
                // reset the left and right counter when we have
                // invalid parentheses substring
                left = 0;
                right = 0;
            }
        }

        return maxLength;
    }
};

Golang solution

// Main function to return the length of
// the longest valid parentheses
func longestValidParentheses(s string) int {
    left, right, maxLength := 0, 0, 0
    n := len(s)

    // iterate the string from left to right
    for  i := 0; i < n; i++ {
        if s[i] == '(' {
            left++
        } else {
            right++
        }

        // if left is equal to right, we found a
        // valid parentheses substring
        if left == right {
            maxLength = max(maxLength, 2 * right)
        } else if (right > left) {
            // reset the left and right counter when we have
            // invalid parentheses substring
            left = 0
            right = 0
        }
    }

    left = 0
    right = 0

    // iterate the string from right to left
    for i := n - 1; i >= 0; i-- {
        if s[i] == '(' {
            left++
        } else {
            right++
        }

        // if left is equal to right, we found a
        // valid parentheses substring
        if left == right {
            maxLength = max(maxLength, 2 * right)
        } else if (left > right) {
            // reset the left and right counter when we have
            // invalid parentheses substring
            left = 0
            right = 0
        }
    }

    return maxLength
}

func max(a, b int) int {
    if a > b {
        return a
    }

    return b
}

JavaScript solution

// Main function to return the length of
// the longest valid parentheses
var longestValidParentheses = function(s) {
    let left = 0, right = 0, maxLength = 0;
    let n = s.length;

    // iterate the string from left to right
    for(let i = 0; i < n; i++) {
        if(s[i] == '(') {
            left++;
        } else {
            right++;
        }

        // if left is equal to right, we found a
        // valid parentheses substring
        if(left == right) {
            maxLength = Math.max(maxLength, 2 * right);
        } else if (right > left) {
            // reset the left and right counter when we have
            // invalid parentheses substring
            left = 0;
            right = 0;
        }
    }

    left = 0;
    right = 0;

    // iterate the string from right to left
    for(let i = n - 1; i >= 0; i--) {
        if(s[i] == '(') {
            left++;
        } else {
            right++;
        }

        // if left is equal to right, we found a
        // valid parentheses substring
        if(left == right) {
            maxLength = Math.max(maxLength, 2 * right);
        } else if (left > right) {
            // reset the left and right counter when we have
            // invalid parentheses substring
            left = 0;
            right = 0;
        }
    }

    return maxLength;
};

Dry Run

Let’s dry-run our algorithm to see how the solution works.

Originally posted at https://alkeshghorpade.me.

Programming
Algorithms
Leetcode
Golang
JavaScript

--

--

Alkesh Ghorpade
Nerd For Tech

Written by Alkesh Ghorpade

137 Followers

Software Engineer. Working ShakaCode. My portfolio https://alkeshghorpade.me

Help

Status

About

Careers

Press

Blog

Privacy

Terms

Text to speech

Teams