LeetCode 32 Longest Valid Parentheses problem solution

LeetCode problem link: 32. Longest Valid Parentheses


LeetCode 32. Longest Valid Parentheses problem description

Hard level problem.


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

1. A substring is a contiguous non-empty sequence of characters within a string.


Example 1:


Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".


Example 2:


Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".


Example 3:


Input: s = ""
Output: 0


Constraints

  • 0 <= s.length <= 3 * 104
  • s[i] is '(' or ')'.

LeetCode 32. Longest Valid Parentheses problem solution

We use a stack to store indices instead of parentheses themselves.

Start with -1 in the stack. It acts as the index before the beginning of a possible valid substring.

For each character:

  • If it is '(', push its index onto the stack.
  • If it is ')', pop one index.
  • If the stack becomes empty, push the current index because this ')' cannot be part of a valid substring and becomes the new boundary.
  • Otherwise, the current valid substring starts after the index at the top of the stack, so its length is i - stack.top().

Keep the maximum length found.


Patterns | Techniques | Data Structures

Stack - Data Structure


Complexity

Time Complexity: O(n)

We scan the string once. Each index is pushed onto the stack at most once and popped at most once, so the total number of stack operations is O(n).


Space Complexity: O(n)

In the worst case, the stack can contain all indices of the string, for example:

(((((

Therefore, the extra space is O(n).


LeetCode 32. Longest Valid Parentheses problem: example

Consider:

s = ")()())"

Initialize:

stack = [-1]
maxLength = 0

Index 0: ')'

Pop the top value:

stack = []

The stack is empty, so this ')' cannot be matched.
Push its index as the new boundary:

stack = [0]
maxLength = 0

Index 1: '('

Push the index:

stack = [0, 1]
maxLength = 0

Index 2: ')'

Pop the matching '(' index:

stack = [0]

The stack is not empty, so calculate:

length = 2 - 0 = 2

The valid substring is:

()

Update:

maxLength = 2

Index 3: '('

Push the index:

stack = [0, 3]
maxLength = 2

Index 4: ')'

Pop the matching '(' index:

stack = [0]

Calculate the current valid length:

length = 4 - 0 = 4

The valid substring is:

()()

Update:

maxLength = 4

Index 5: ')'

Pop:

stack = []

The stack becomes empty, so index 5 becomes the new boundary:

stack = [5]

Final result is 4.

The longest valid parentheses substring is:

()()

LeetCode 32 C++ solution

class Solution {
public:
    int longestValidParentheses(string s) {
        // Store indices. -1 is the initial boundary.
        stack<int> st;
        st.push(-1);

        int maxLength = 0;

        for(int i = 0; i < s.size(); i++) {
            if(s[i] == '(') {
                // Save the index of an unmatched opening parenthesis.
                st.push(i);
            } else {
                // Try to match the current closing parenthesis.
                st.pop();

                if(st.empty()) {
                    // No valid substring can cross this index.
                    // Use it as the new boundary.
                    st.push(i);
                } else {
                    // The valid substring starts after st.top().
                    maxLength = max(maxLength, i - st.top());
                }
            }
        }

        return maxLength;
    }
};

LeetCode 32 Java solution

class Solution {
    public int longestValidParentheses(String s) {
        // Store indices. -1 is the initial boundary.
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);

        int maxLength = 0;

        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '(') {
                // Save the index of an unmatched opening parenthesis.
                stack.push(i);
            } else {
                // Try to match the current closing parenthesis.
                stack.pop();

                if(stack.isEmpty()) {
                    // No valid substring can cross this index.
                    // Use it as the new boundary.
                    stack.push(i);
                } else {
                    // The valid substring starts after stack.peek().
                    maxLength = Math.max(maxLength, i - stack.peek());
                }
            }
        }

        return maxLength;
    }
}

LeetCode 32 JavaScript solution

var longestValidParentheses = function(s) {
    // Store indices. -1 is the initial boundary.
    const stack = [-1];

    let maxLength = 0;

    for(let i = 0; i < s.length; i++) {
        if(s[i] === '(') {
            // Save the index of an unmatched opening parenthesis.
            stack.push(i);
        } else {
            // Try to match the current closing parenthesis.
            stack.pop();

            if(stack.length === 0) {
                // No valid substring can cross this index.
                // Use it as the new boundary.
                stack.push(i);
            } else {
                // The valid substring starts after the top index.
                maxLength = Math.max(
                    maxLength,
                    i - stack[stack.length - 1]
                );
            }
        }
    }

    return maxLength;
};

LeetCode 32 TypeScript solution

function longestValidParentheses(s: string): number {
    // Store indices. -1 is the initial boundary.
    const stack: number[] = [-1];

    let maxLength = 0;

    for(let i = 0; i < s.length; i++) {
        if(s[i] === '(') {
            // Save the index of an unmatched opening parenthesis.
            stack.push(i);
        } else {
            // Try to match the current closing parenthesis.
            stack.pop();

            if(stack.length === 0) {
                // No valid substring can cross this index.
                // Use it as the new boundary.
                stack.push(i);
            } else {
                // The valid substring starts after the top index.
                maxLength = Math.max(
                    maxLength,
                    i - stack[stack.length - 1]
                );
            }
        }
    }

    return maxLength;
}

LeetCode 32 Python solution

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        # Store indices. -1 is the initial boundary.
        stack = [-1]

        max_length = 0

        for i in range(len(s)):
            if s[i] == '(':
                # Save the index of an unmatched opening parenthesis.
                stack.append(i)
            else:
                # Try to match the current closing parenthesis.
                stack.pop()

                if not stack:
                    # No valid substring can cross this index.
                    # Use it as the new boundary.
                    stack.append(i)
                else:
                    # The valid substring starts after stack[-1].
                    max_length = max(max_length, i - stack[-1])

        return max_length