Longest Valid Parentheses Solution for Accenture

Company: Accenture · Difficulty: Medium · Topics: String, Stack, Dynamic Programming

Problem Statement

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

Key Understanding:

• Valid parentheses must be balanced (equal number of '(' and ')')
• Valid parentheses must be properly nested
• We need to find the longest substring that is valid
• The substring must be contiguous
• We need to handle edge cases like starting with ')'

Examples

Example 1:

Input: s = "(()"

Output: 2

Explanation:

• The longest valid parentheses substring is "()"
• Starting from index 1: "(()" → "()" (length 2)
• The substring "(()" is not valid because it's not balanced
• Visual representation: "(()" → [invalid, valid, invalid]

Example 2:

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

Output: 4

Explanation:

• The longest valid parentheses substring is "()()"
• Starting from index 1: ")()())" → "()()" (length 4)
• Other valid substrings: "()" (length 2)
• Visual representation: ")()())" → [invalid, valid, valid, valid, valid, invalid]

Example 3:

Input: s = ""

Output: 0

Explanation:

• Empty string has no valid parentheses
• Length is 0

Example 4:

Input: s = "((()"

Output: 2

Explanation:

• The longest valid parentheses substring is "()"
• Starting from index 2: "((()" → "()" (length 2)
• The substring "((()" is not valid because it's not balanced

Example 5:

Input: s = "()(()"

Output: 2

Explanation:

• The longest valid parentheses substring is "()"
• Starting from index 0: "()(()" → "()" (length 2)
• The substring "()(()" is not valid because it's not balanced

Intuition

The key insight is that valid parentheses must be balanced and consecutive. We can use a stack to keep track of indices of opening parentheses and calculate the length of valid substrings.

Core Concept:

• Valid parentheses must have matching pairs
• We can use a stack to track opening parentheses
• When we find a closing parenthesis, we can calculate the length
• We need to handle edge cases properly

Why Stack Works:

• Stack naturally handles the LIFO (Last In, First Out) property of parentheses
• When we see '(', we push its index
• When we see ')', we pop the last '(' and calculate length
• This ensures we find the longest valid substring

Mathematical Insight:

• For a valid substring, the number of '(' and ')' must be equal
• The substring must start and end with balanced parentheses
• We can calculate length as current_index - stack_top_index

Approach

Approach 1: Stack (Optimal)

Algorithm:

1. Initialize stack with -1 to handle edge cases

2. For each character in the string:

• If '(', push current index to stack
• If ')', pop from stack and calculate length
• If stack becomes empty, push current index

3. Keep track of maximum length found

Why This Works:

• We use -1 as initial stack value to handle cases starting with ')'
• When we pop, we calculate length as current_index - stack_top
• This gives us the length of valid substring ending at current position
• We update our answer if we find a longer valid substring

Complexity Analysis:

• Time: O(n) - Single pass through the string
• Space: O(n) - Stack can store up to n elements

Approach 2: Dynamic Programming

Algorithm:

1. Create DP array where dp[i] represents length of valid parentheses ending at i

2. For each ')', check if there's a matching '('

3. Update DP array and track maximum

Why This Works:

• We use dynamic programming to store lengths of valid substrings
• For each position, we check if we can extend a previous valid substring
• This approach is more complex but gives us insight into the structure

Complexity Analysis:

• Time: O(n) - Single pass through the string
• Space: O(n) - DP array of size n

Approach 3: Two Pass Approach

Algorithm:

1. Scan from left to right counting '(' and ')'

2. Scan from right to left counting '(' and ')'

3. Track maximum valid length

Why This Works:

• We count parentheses in both directions
• This helps us find the longest valid substring
• We handle edge cases by scanning in both directions

Complexity Analysis:

• Time: O(n) - We traverse the string twice
• Space: O(1) - Only constant variables needed

Dry Run

Let's trace through Example 2: s = ")()())"

Stack Approach:

Step 1: Initialize

• Stack: [-1] (initialized with -1)
• maxLength = 0

Step 2: Process each character

• i=0, char=')':
• Pop -1 from stack
• Stack becomes empty
• Push 0 to stack
• Stack: [0]
• i=1, char='(':
• Push 1 to stack
• Stack: [0, 1]
• i=2, char=')':
• Pop 1 from stack
• Length = 2 - 0 = 2
• maxLength = max(0, 2) = 2
• Stack: [0]
• i=3, char='(':
• Push 3 to stack
• Stack: [0, 3]
• i=4, char=')':
• Pop 3 from stack
• Length = 4 - 0 = 4
• maxLength = max(2, 4) = 4
• Stack: [0]
• i=5, char=')':
• Pop 0 from stack
• Stack becomes empty
• Push 5 to stack
• Stack: [5]

Step 3: Return maxLength = 4

Dynamic Programming Approach:

Step 1: Initialize DP array

• dp = [0, 0, 0, 0, 0, 0]

Step 2: Process each character

• i=0, char=')': dp[0] = 0 (no matching '(')
• i=1, char='(': dp[1] = 0 (no matching ')')
• i=2, char=')':
• Check if s[1] == '('
• dp[2] = dp[0] + 2 = 0 + 2 = 2
• i=3, char='(': dp[3] = 0 (no matching ')')
• i=4, char=')':
• Check if s[3] == '('
• dp[4] = dp[2] + 2 = 2 + 2 = 4
• i=5, char=')': dp[5] = 0 (no matching '(')

Step 3: Return max(dp) = 4

Key Insights

1. Stack Property: Stack naturally handles parentheses matching

2. Index Tracking: We track indices to calculate substring lengths

3. Edge Case Handling: Initialize stack with -1 for proper length calculation

4. Consecutive Nature: Valid parentheses must be consecutive

5. Balanced Property: Equal number of '(' and ')' in valid substring

Edge Cases

1. Empty String: Return 0

2. Single Character: Return 0 (no valid parentheses)

3. Starting with ')': Handle with stack initialization

4. All '(': Return 0 (no closing parentheses)

5. All ')': Return 0 (no opening parentheses)

6. Nested Parentheses: Algorithm handles nested cases correctly

Solution

⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.

Solution 1: Stack (Optimal)

Time Complexity: O(n) - We traverse the string once

Space Complexity: O(n) - Stack can store up to n elements

Advantages:

• Most intuitive approach
• Handles all edge cases naturally
• Easy to understand and implement
• Efficient time complexity

Disadvantages:

• Uses extra space for stack
• Slightly more complex than other approaches

Solution 2: Dynamic Programming

Time Complexity: O(n) - We traverse the string once

Space Complexity: O(n) - DP array of size n

Advantages:

• Systematic approach
• Good for understanding the problem structure
• Can be extended to other parentheses problems

Disadvantages:

• More complex implementation
• Uses extra space

Solution 3: Two Pass Approach

Time Complexity: O(n) - We traverse the string twice

Space Complexity: O(1) - We use only constant extra space

Advantages:

• Constant space usage
• Simple implementation
• Good for memory-constrained environments

Disadvantages:

• Traverses string twice
• Less intuitive than stack approach

More Accenture coding questions