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. Given the following Python code for asteroid collision, what is the output when the input is [8, -8, 5, -10]?

def asteroidCollision(asteroids):
    stack = []
    for a in asteroids:
        alive = True
        while alive and stack and stack[-1] > 0 and a < 0:
            if stack[-1] < -a:
                stack.pop()
            elif stack[-1] == -a:
                stack.pop()
                alive = False
            else:
                alive = False
        if alive:
            stack.append(a)
    return stack

print(asteroidCollision([8, -8, 5, -10]))

easy

A. [5, -10]

B. [-10]

C. [8, 5, -10]

D. []

Solution

1. Step 1: Trace collision between 8 and -8

   8 and -8 are equal size but opposite direction, both explode -> stack empty.

2. Step 2: Process 5 and then -10

   5 is pushed; -10 collides with 5, since 10 > 5, 5 pops, -10 remains and is pushed.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Final stack contains only [-10] after resolving collisions [OK]

Hint: Equal size opposite asteroids both explode [OK]

Common Mistakes:

• Forgetting to pop both equal asteroids
• Appending asteroid after it exploded
• Not handling multiple collisions in while loop

2. Consider the following Python code that evaluates Reverse Polish Notation expressions. What is the final output when the input tokens are ["4", "13", "5", "/", "+"]?

class Solution:
    def evalRPN(self, tokens):
        import operator
        ops = {
            '+': operator.add,
            '-': operator.sub,
            '*': operator.mul,
            '/': lambda x, y: int(x / y),
        }
        stack = []
        for token in tokens:
            if token in ops:
                right = stack.pop()
                left = stack.pop()
                stack.append(ops[token](left, right))
            else:
                stack.append(int(token))
        return stack.pop()

sol = Solution()
print(sol.evalRPN(["4", "13", "5", "/", "+"]))

easy

A. 2

B. 6

C. 8

D. 10

Solution

1. Step 1: Trace stack operations

   Push 4, push 13, push 5; then '/' operator pops 5 and 13, computes int(13/5) = 2, push 2; then '+' operator pops 2 and 4, computes 4+2=6, push 6.

2. Step 2: Final stack pop

   Pop the last element 6 as the result.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Stack correctly reflects intermediate results [OK]

Hint: Remember integer division truncates toward zero [OK]

Common Mistakes:

• Swapping left and right operands
• Using float division instead of int
• Off-by-one in stack pops

3. Consider this buggy version of the decodeString function. Which line contains the subtle bug that causes incorrect decoding for inputs with multiple bracketed substrings?

medium

A. Line appending current_string to string_stack

B. Line popping count from count_stack

C. Line resetting k after '[' is missing

D. Line appending characters to current_string

Solution

1. Step 1: Identify where repeat count is reset

   After pushing k to count_stack on '[', k must be reset to 0 to avoid carryover to next substring.

2. Step 2: Locate missing reset

   The code comment indicates missing reset of k after pushing it, causing subsequent repeats to accumulate incorrectly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Resetting k prevents repeat count carryover bugs [OK]

Hint: Repeat count must reset after pushing to stack [OK]

Common Mistakes:

• Forgetting to reset repeat count after '['
• Mismanaging stack push/pop order

4. What is the time complexity of the optimized monotonic stack solution for the sum of subarray minimums problem, and why?

medium

A. O(n log n) due to sorting or binary search inside the stack operations

B. O(n^2) because each element can be pushed and popped multiple times

C. O(n) because each element is pushed and popped at most once

D. O(n) but with O(n^2) auxiliary space for storing subarray minimums

Solution

1. Step 1: Identify stack operations per element

   Each element is pushed once and popped once, so total stack operations are O(n).

2. Step 2: Confirm no nested loops or extra sorting

   The algorithm uses a single pass with a stack, no sorting or nested loops, so time is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Monotonic stack guarantees linear time complexity [OK]

Hint: Each element pushed and popped once -> O(n) time [OK]

Common Mistakes:

• Assuming multiple pops per element cause O(n^2)
• Confusing with sorting-based methods

5. If the input matrix can contain '2's representing cells that can be counted as either 0 or 1 (i.e., flexible cells), which modification to the maximalRectangle algorithm is correct to find the largest rectangle of 1s considering '2' as 1 or 0?

hard

A. Treat '2' as '1' in all rows and run the standard maximalRectangle algorithm once.

B. Use backtracking to try all combinations of '2' as '0' or '1' and find the maximal rectangle.

C. Modify the histogram update to count '2' as 0.5 height and adjust largestRectangleArea accordingly.

D. Run maximalRectangle twice: once treating '2' as '1' and once as '0', then take the max area.

Solution

1. Step 1: Understand the flexibility of '2' cells

   Each '2' can be either 0 or 1, so multiple configurations exist.

2. Step 2: Evaluate naive approaches

   Treating all '2's as 1 or 0 misses mixed configurations; running twice is insufficient.

3. Step 3: Correct approach

   Backtracking or bitmasking all combinations of '2' assignments is needed to find the true maximal rectangle.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Only exhaustive search guarantees correctness with flexible cells [OK]

Hint: Flexible cells require exploring all assignments [OK]

Common Mistakes:

• Assuming fixed assignment for '2'
• Partial runs miss mixed cases
• Fractional heights invalid for stack approach