Search⌘ K
AI Features
Home
Courses
Coderust: Hacking the Coding Interview

Longest Valid Parentheses

Explore methods to identify the longest valid parentheses substring within a string by using two passes that count left and right parentheses. Understand how to handle edge cases and optimize for time and space complexity.

We'll cover the following...

Statement

Given a string that contains the characters '(' and ')', find the length of the longest valid parentheses substring.

Example

Let’s look at the image below:

g array ( ( )

The longest valid parentheses substring in "(()" is "()", which has a length of 2.

Sample input

s = "(()"

Expected output

2

Try it yourself

#include <iostream>
#include <string>
using namespace std;
int LongestValidParentheses(string s) {
    // TODO: Write - Your - Code
    return -1;
}

Solution

We can solve this problem with two passes over the input string. As we traverse the string from left to right, we count the number of left parentheses (left) and right parentheses (right). If at any point, we see more right parentheses than left parentheses, we can be certain that the sub-string we’ve seen so far can’t be part of the longest valid parenthesization. In ...