Skip to main content

Leetcode 32: Longest Valid Parentheses

 

1. Problem Statement (Simple Explanation):

You are given a string s containing only:

  • '('

  • ')'

You must return the length of the longest valid (well-formed) parentheses substring.

  • A valid substring must be contiguous.

  • It must be a correct parentheses sequence (every '(' has a matching ')' in proper order).


2. Examples:


Example 1:

Input: s = "(()"

Valid substrings:

  • "()" (from index 1 to 2) – length 2

Longest length: 2

Output: 2


Example 2:

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

Valid substrings:

  • "()()" (from index 1 to 4) – length 4

  • "()" (from index 1 to 2)

  • "()" (from index 3 to 4)

Longest length: 4

Output: 4


Example 3:

Input: s = ""

No parentheses → no valid substring.

Output: 0


Constraints:

  • 0 ≤ ∣s∣ ≤ 3*104

  • s[i] is '(' or ')'.


3. Approaches Overview:


There are three classic approaches:

  1. Stack-based – O(n) time, O(n) space.

  2. Two-pass counters (left-to-right and right-to-left) – O(n) time, O(1) space.

  3. Dynamic programming – O(n) time, O(n) space.


4. Approach 1 – Stack with Indices (O(n), Easy to Reason):


Intuition:

  • Use a stack that stores indices of characters.

  • Use it to track boundaries between valid substrings.


Trick:

  • Push -1 initially to represent a "base" before the start of the string.

  • When you see '(', push its index.

  • When you see ')':

    • Pop the stack (matching a previous '(' if possible).

    • If the stack becomes empty after popping:

      • Push current index as a new base (this ')' is an unmatched right boundary).

    • Else:

      • Current valid substring length = i - stack.top()

      • Update max.

This works because:

  • stack.top() always holds the index just before the start of the current valid segment.


Algorithm (Step-by-Step):


  1. Initialize:

    • maxLen = 0

    • Stack st

    • Push -1 onto st (base index).

  2. For each index i in 0..n-1:

    • If s[i] == '(':

      • Push i onto stack.

    • Else (s[i] == ')'):

      • Pop the stack:

        • If stack becomes empty:

          • Push i as a new base.

        • Else:

          • len = i - st.top()

          • maxLen = max(maxLen, len)

  3. Return maxLen.


Pseudo-code (Stack):



Complexity:

  • Time: O(n)

  • Space: O(n) in worst case (all '(').


5. Approach 2 – Two-pass Scan with Counters (O(n), O(1) Space):


This is a very elegant solution and space-optimal.


Intuition:

We track counts of '(' and ')' while scanning:

  1. Left to Right:

    • left = 0, right = 0

    • For each char:

      • If '(' → left++

      • If ')' → right++

    • If left == right:

      • Valid substring length = 2 * right

    • If right > left:

      • Reset both counts to 0 (too many ')' → invalid).

This catches valid segments where we never see more ')' than '(' (like well-formed from the left). But it misses cases that end with more '(' (like "(()"), since we only reset on extra ')'.

  1. Right to Left:

    • Same idea, but swap roles:

    • left = 0, right = 0

    • Scan from right to left:

      • If '(' → left++

      • If ')' → right++

    • If left == right:

      • Valid substring length = 2 * left

    • If left > right:

      • Reset both counts (too many '(' from this side).

Combining both scans handles all cases.


Pseudo-code (Two-pass):



Complexity:

  • Time: O(n)

  • Space: O(1)


6. Java (Stack Solution) code:



7. C (Stack via Array) code:



8. C++ (Stack) code:



9. Python (Stack) code:



10. JavaScript (Stack) code:


Comments

Post a Comment

Popular posts from this blog

Leetcode 1: Two Sum

  Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to  return the indices of two numbers in the array  such that: Conditions: Each input has  exactly one solution . You  cannot use the same element twice . You can return the answer in  any order . 2. Examples Example 1 Input:                                    nums = [2, 7, 11, 15], target = 9 Output:                                 [0, 1] Explanation:                     nums[0]+nums[1]=2+7=9              So we return [0, 1]. Example 2 Input:           ...
Post a Comment
Read more

Leetcode 3: Longest Substring Without Repeating Characters

  Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not  contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input:   s = "pwwkew" Output:   3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...
Post a Comment
Read more

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given  two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a  single digit . The digits are stored in  reverse order  (i.e., the 1’s digit is at the head). You need to  add the two numbers  and return the  sum as a linked list , also in reverse order. You can assume: There are  no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input:                l1 = [2,4,3]                l2 = [5,6,4]           Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output:                [7,0,8] Explanation:        ...
Post a Comment
Read more