Longest Valid Parentheses - Practice Coding Problems

Longest Valid Parentheses - Problem

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

A valid parentheses substring means every opening parenthesis has a corresponding closing parenthesis in the correct order, with no unmatched parentheses.

Examples:

"(()": longest valid substring is "()" with length 2
")()())": longest valid substring is "()()" with length 4
"": empty string returns 0

Input & Output

Example 1 — Mixed Valid and Invalid

$ Input: s = ")()())"

› Output: 4

💡 Note: The longest valid parentheses substring is "()()", which has length 4. It appears in the middle of the string.

Example 2 — Simple Valid Pair

$ Input: s = "(()"

› Output: 2

💡 Note: The longest valid parentheses substring is "()", which has length 2.

Example 3 — Empty String

$ Input: s = ""

› Output: 0

💡 Note: An empty string contains no valid parentheses, so the length is 0.

Constraints

0 ≤ s.length ≤ 3 × 10⁴
s[i] is '(' or ')'.

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

String with opening '(' and closing ')' parentheses

Find Valid Substrings

Identify all properly matched parentheses

Return Maximum Length

Length of longest valid substring found

Key Takeaway

🎯 Key Insight: Track lengths of valid parentheses ending at each position to build up the solution efficiently

Asked in

G Google 45 a Amazon 38 f Facebook 32 M Microsoft 28

The key insight is to track the length of valid parentheses sequences efficiently. Best approach is Dynamic Programming with O(n) time and space, building up valid lengths incrementally. Alternative approaches include stack-based tracking and two-pointer counting for O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Substrings	O(n³)	O(1)	Check every possible substring for valid parentheses
Stack-Based Approach	O(n)	O(n)	Use stack to track indices and find valid parentheses ranges
Dynamic Programming	O(n)	O(n)	Build up solution using 1D DP array to track valid lengths
Two-Pointer Counting	O(n)	O(1)	Count opening and closing parentheses with two passes

Brute Force - Check All Substrings — Algorithm Steps

Step 1: Try every possible starting position
Step 2: For each start, try every possible ending position
Step 3: Check if substring has valid parentheses
Step 4: Keep track of maximum valid length

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate All Substrings

Try every starting and ending position

Validate Each Substring

Count opening/closing brackets

Track Maximum

Keep the longest valid length found

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool isValid(const char* substr, int len) {
    int count = 0;
    for (int i = 0; i < len; i++) {
        if (substr[i] == '(') {
            count++;
        } else {
            count--;
            if (count < 0) return false;
        }
    }
    return count == 0;
}

int solution(char* s) {
    int maxLen = 0;
    int n = strlen(s);
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 2; j <= n; j += 2) {  // Only even lengths
            if (isValid(s + i, j - i)) {
                if (j - i > maxLen) {
                    maxLen = j - i;
                }
            }
        }
    }
    
    return maxLen;
}

int main() {
    char s[30001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;  // Remove newline
    
    int result = solution(s);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Two nested loops for all substrings O(n²), plus O(n) to validate each substring

⚠ Quadratic Growth

Space Complexity

O(1)

Only using a few variables for tracking

✓ Linear Space

277.9K Views

High Frequency

~25 min Avg. Time

8.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Substrings — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler