Longest Valid Parentheses

The Longest Valid Parentheses on leetcode is ranked as a hard problem. At first, it might seem like there are trickeries to solving this problem… let’s dive in.

The challenge description:

Given a string containing just the characters ‘(’ and ‘)’, return the length of the longest valid (well-formed) parentheses substring

Their example inputs and outputs describe it pretty well:

	

		

			Toggle
Numbering
			Copy
		
	

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

Alright, so we’re not looking to return a string or structure or anything complex… we just need a number.

There are a few ways we can approach this problem, but there are two methods I particularly like:

• The two pointers
• Using a stack

The stack is a simple approach (and easy to describe).

Using a stack, we can iterate through every character of the string and check if it’s a ( or ) character (the problem description says the only characters present will be either a ( or ), so we don’t have to worry about any other characters).

If we see a (, we’ll push the index to the stack. Why the index? We’ll iterate through every character and take the longest sequence as the last valid place, if we’re in a valid spot.

If we see a ), we’ll pop off an index from our stack (we can disregard it, we’re not interested in the value) we know we’re in one of two places:

1. Our stack is empty and we’re starting a new closing bracket
2. Our stack isn’t empty yet and we have to compute the next longest max

Let’s hit the solution

I’ll be writing this up in rust, but it is easily translatable to other languages – Try it!

Implementation

	

		

			Toggle
Numbering
			Copy
		
	

	
impl Solution {
    pub fn longest_valid_parentheses(s: String) -> i32 {
        0
    }
}

Since we’ll be working with a number as a return value, we’ll need to keep track of the maximum number of valid parenthese. We’re also using a stack, so let’s create a Vec to hold our values. One final trick to make the solution a bit simpler by adding the first value as a -1:

	

		

			Toggle
Numbering
			Copy
		
	

	
impl Solution {
    pub fn longest_valid_parentheses(s: String) -> i32 {
        let mut max = 0;
        let mut stack: Vec<i32> = Vec::new();
        stack.push(-1);

        // Iterate through the characters, one by 1
        for (idx, c) in s.chars().enumerate() {
            // Check if the character is a `(` character
            if c == '(' {
                // Push the index of the character on to the stack
                stack.push(i as i32);
            } else {
                // otherwise the character is a closing bracket )
                stack.pop();
                // Case 1
                if stack.is_empty() {
                    // Since the string could open with a ), we
                    // still need to add it to the stack
                    stack.push(i as i32);
                } else {
                    // Complex-ish line:
                    // We take the maxium value of the current value or
                    // of the calculation of the current index and the
                    // last index of a (
                    max = max.max(i as i32 - stack.last().unwrap());
                }
            }
        }
        max
    }
}