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 ...