Longest Valid Parentheses

📋

Problem

Imagine you are building a code editor that highlights the longest balanced parentheses substring to help developers spot syntax errors quickly.

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

1 ≤ s.length ≤ 10^5s consists only of '(' and ')'

Edge cases: All '(' characters → 0All ')' characters → 0Alternating parentheses but no valid pairs, e.g. ')(' → 0

</>

IDE

def longestValidParentheses(s: str) -> int:public int longestValidParentheses(String s)int longestValidParentheses(string s)function longestValidParentheses(s)

def longestValidParentheses(s: str) -> int:
    # Write your solution here
    pass

class Solution {
    public int longestValidParentheses(String s) {
        // Write your solution here
        return 0;
    }
}

#include <string>
using namespace std;

int longestValidParentheses(string s) {
    // Write your solution here
    return 0;
}

function longestValidParentheses(s) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Failing to detect any valid substring due to incorrect stack initialization or missing updates.✅ Initialize stack with -1 and update max length after each valid pop.

Wrong: length less than actual maxGreedy approach stopping at first invalid character instead of continuing to find longer valid substrings.✅ Use stack to track indices and update max length after each valid pop, not stopping early.

Wrong: non-zero for empty or single char inputNot handling base cases properly, counting unmatched parentheses as valid.✅ Add base case checks for empty and single character strings returning 0.

Wrong: off-by-one errors in length calculationIncorrect index difference calculation when updating max length.✅ Calculate length as current index minus top of stack after popping.

Wrong: TLE on large inputsUsing brute force or O(n^2) approach instead of O(n) stack or two-pointer method.✅ Implement linear time stack or two-pointer solution.

✓

Test Cases

Focus on handling base cases like empty strings and single characters correctly.

Watch out for common pitfalls like greedy counting and off-by-one errors.

Optimize your solution to linear time to handle large inputs efficiently.

t1_01basic

Input{"s":"(()"}

Expected2

⏱ Performance - must finish in 2000ms

The longest valid parentheses substring is "()" with length 2.

💡 Consider using a stack to track indices of '(' characters.

💡 Push indices of '(' and pop when you find a matching ')'.

💡 Keep track of the longest valid substring length using indices on the stack.

Why it failed: Output less than 2 means missing valid substring detection; fix by correctly updating max length when popping stack.

✓ Correctly identifies longest valid substring length.

t1_02basic

Input{"s":")()())"}

Expected4

⏱ Performance - must finish in 2000ms

The longest valid parentheses substring is "()()" with length 4.

💡 Watch for unmatched ')' that reset the start index.

💡 Use a stack initialized with -1 to handle base cases.

💡 Update max length as current index minus top of stack after popping.

Why it failed: Output less than 4 means failing to handle unmatched ')' properly; fix by initializing stack with -1 and updating max length accordingly.

✓ Correctly handles unmatched parentheses and computes max length.

t2_01edge

Input{"s":""}

Expected0

⏱ Performance - must finish in 2000ms

Empty string has no valid parentheses, so length is 0.

💡 Check how your code handles empty input strings.

💡 Ensure no index errors or invalid stack operations occur.

💡 Return 0 immediately if string length is zero.

Why it failed: Non-zero output means not handling empty string correctly; fix by adding base case for empty input.

✓ Correctly returns 0 for empty input.

t2_02edge

Input{"s":"("}

Expected0

⏱ Performance - must finish in 2000ms

Single '(' cannot form valid parentheses substring, so length is 0.

💡 Single character strings cannot form valid pairs.

💡 Check that your code does not count unmatched '(' as valid.

💡 Return 0 if no valid pairs found.

Why it failed: Output > 0 means counting unmatched '(' as valid; fix by verifying pairs before counting length.

✓ Correctly returns 0 for single unmatched '(' character.

t2_03edge

Input{"s":"()()()"}

Expected6

⏱ Performance - must finish in 2000ms

Entire string is valid parentheses, length is full string length 6.

💡 Check if your code can handle multiple consecutive valid pairs.

💡 Ensure max length updates correctly for continuous valid substrings.

💡 Use stack or counters to track continuous valid sequences.

Why it failed: Output less than 6 means failing to accumulate continuous valid pairs; fix by updating max length after each valid pair.

✓ Correctly identifies full string as valid parentheses substring.

t3_01corner

Input{"s":"(()))())("}

Expected4

⏱ Performance - must finish in 2000ms

Longest valid substring is "()()" or "(())" with length 4.

💡 Beware of greedy approaches that stop at first invalid character.

💡 Use stack to track indices and update max length after each valid pop.

💡 Reset start index or stack base when unmatched ')' found.

Why it failed: Output greater than 4 means greedy approach incorrectly counts invalid substrings; fix by using stack-based index tracking.

✓ Correctly handles complex invalid sequences and finds max valid length.

t3_02corner

Input{"s":"((((((((((("}

Expected0

⏱ Performance - must finish in 2000ms

All '(' characters with no matching ')' results in 0 valid length.

💡 Check that unmatched '(' do not contribute to valid length.

💡 Stack should not count leftover '(' as valid.

💡 Return 0 if no valid pairs found.

Why it failed: Output > 0 means counting unmatched '(' as valid; fix by verifying stack emptiness before counting.

✓ Correctly returns 0 for all '(' input.

t3_03corner

Input{"s":")()())()()("}

Expected4

⏱ Performance - must finish in 2000ms

Longest valid substring is "()()" with length 4, despite invalid characters at start and end.

💡 Watch for off-by-one errors in index calculations.

💡 Initialize stack with -1 to handle base cases correctly.

💡 Update max length after each valid pop using current index minus stack top.

Why it failed: Output less than 4 means off-by-one error in length calculation; fix by careful index difference calculation.

✓ Correctly computes max length with proper index handling.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Input length n=100000, solution must run in O(n) time within 2 seconds.

💡 Brute force O(n^3) will time out on large inputs.

💡 Use stack or two-pointer linear scan approach for O(n) time.

💡 Avoid nested loops and repeated substring checks.

Why it failed: TLE indicates using brute force or O(n^2) approach; fix by implementing O(n) stack or two-pass solution.

✓ Solution runs in O(n) time confirming efficient approach.

Practice

1. You receive a continuous stream of lowercase letters and need to report the first character that appears exactly once at each step. Which approach guarantees an optimal O(n) time solution with constant space for this problem?

easy

A. Use a dynamic programming approach to store subproblems of unique characters at each prefix of the stream.

B. Use a brute force scan of the entire stream so far to find the first unique character after each new letter.

C. Maintain a fixed-size frequency array for all lowercase letters and a queue to track potential unique characters, updating both as new letters arrive.

D. Use a greedy approach that picks the first character that hasn't appeared before without tracking frequencies.

Solution

1. Step 1: Understand problem constraints

   The stream consists of lowercase letters only, so a fixed-size frequency array of length 26 suffices.

2. Step 2: Identify optimal approach

   Using a frequency array plus a queue to track candidates for first unique character allows O(1) updates per character and O(n) total time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Frequency array + queue approach is standard for this problem [OK]

Hint: Frequency array + queue yields O(n) time and O(1) space [OK]

Common Mistakes:

• Thinking brute force scanning is efficient enough
• Assuming DP applies here
• Using greedy without frequency tracking

2. You need to design a data structure that supports push, pop, top, and retrieving the minimum element in constant time. Which approach guarantees all operations run in O(1) time without scanning the entire stack for the minimum each time?

easy

A. Use a brute force stack and scan the entire stack to find the minimum on each getMin call.

B. Use a dynamic programming table to store minimums for all sub-stacks and update it on each push/pop.

C. Keep two stacks: one for all elements and one for minimum elements, pushing to the min stack only when a new minimum is found.

D. Maintain a single stack that stores the difference between the pushed value and the current minimum, updating the minimum accordingly.

Solution

1. Step 1: Understand the problem constraints

   The goal is to achieve O(1) time for all operations including getMin, without scanning the entire stack.

2. Step 2: Evaluate approaches

   Brute force scanning is O(n), dynamic programming is unnecessary and inefficient, two stacks approach works but uses extra space. The single stack with encoded differences stores relative values and updates min in O(1) time and space efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Single stack encoding achieves O(1) time and O(n) space with one stack [OK]

Hint: Single stack encoding stores differences for O(1) min retrieval [OK]

Common Mistakes:

• Thinking scanning stack for min is acceptable
• Confusing two-stack approach as optimal space
• Assuming DP is needed for min tracking

3. Consider the following MinStack implementation using a single stack with encoded minimums. After executing the sequence push(3), push(5), push(2), pop(), what is the value returned by getMin()?

easy

A. None

B. 3

C. 5

D. 2

Solution

1. Step 1: Trace push(3)

   Stack empty, push 0, minVal=3.

2. Step 2: Trace push(5)

   diff=5-3=2>0, push 2, minVal=3.

3. Step 3: Trace push(2)

   diff=2-3=-1<0, push -1, minVal=2.

4. Step 4: Trace pop()

   pop -1 (negative), minVal=2 - (-1)=3.

5. Step 5: getMin()

   minVal=3.

6. Final Answer:

   Option B -> Option B

7. Quick Check:

   After popping 2, min is restored to 3 [OK]

Hint: Negative diff updates minVal on push and pop [OK]

Common Mistakes:

• Forgetting to update minVal on pop
• Returning old minVal after pop
• Confusing top value with minVal

4. Consider the following Python code implementing the optimized next greater element algorithm. What is the final output when calling nextGreaterElement([4,1,2], [1,3,4,2])?

easy

A. [-1, -1, 3]

B. [-1, 3, -1]

C. [3, -1, -1]

D. [3, 4, -1]

Solution

1. Step 1: Trace stack and map updates for nums2

   Process nums2: push 1, then 3 > 1 so pop 1 -> map[1]=3; push 3; 4 > 3 pop 3 -> map[3]=4; push 4; 2 < 4 push 2. Stack ends with [4,2].

2. Step 2: Assign -1 for remaining stack elements and build result

   Pop 2 -> map[2]=-1; pop 4 -> map[4]=-1. Result for nums1=[4,1,2] is [map[4], map[1], map[2]] = [-1,3,-1].

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Matches expected output from code comments and manual trace [OK]

Hint: Stack pops smaller elements when a bigger one arrives [OK]

Common Mistakes:

• Confusing order of popping leading to wrong map values
• Forgetting to assign -1 for elements with no next greater
• Mixing up indices when building the final result

5. What is the time complexity of the optimized monotonic stack solution for the Next Greater Element I problem, where m = length of nums1 and n = length of nums2?

medium

A. O(m * n) because for each element in nums1, we scan nums2 to find the next greater element.

B. O(n) because only nums2 is processed with a stack; nums1 lookup is constant time.

C. O(n + m) because each element in nums2 is pushed and popped at most once, and mapping results for nums1 is O(m).

D. O(n log n) due to sorting nums2 before processing.

Solution

1. Step 1: Analyze stack operations on nums2

   Each element in nums2 is pushed once and popped at most once, so stack operations are O(n).

2. Step 2: Analyze mapping and lookup for nums1

   Mapping next greater elements for nums1 uses a hashmap and set lookups, each O(1), done m times, total O(m).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Combined complexity is O(n + m), not O(m*n) or O(n log n) [OK]

Hint: Stack operations are linear; hashmap lookups are constant [OK]

Common Mistakes:

• Assuming nested loops cause O(m*n) complexity
• Confusing sorting-based approaches with stack-based ones
• Ignoring the cost of hashmap lookups