Finding the Length of the Longest Valid Parentheses Substring in LeetCode

Longest Valid Parentheses

Parentheses are commonly used in mathematical expressions to indicate the order of operations. In computer science, they’re also used in algorithms and data structures to define relationships between elements. When dealing with parentheses in strings, it’s often necessary to determine whether they’re well-formed, meaning they open and close in the correct order.

In this blog, we’ll explore a solution to the LeetCode problem of finding the length of the longest valid parentheses substring in a given string.

Understanding the Problem

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

Given a string containing just the characters ‘(‘ and ‘)’, the goal is to return the length of the longest valid (well-formed) parentheses substring. A valid parentheses substring is defined as a substring that consists of only ‘(‘ and ‘)’ characters, and in which every ‘)’ is preceded by a ‘(‘.

Approach

There are several approaches that can be used to solve this problem, but the stack-based approach is a common and effective solution. In this approach, we’ll use a stack to store the indices of the parentheses characters as we iterate through the string.

To start, we’ll initialize a stack and push the index -1 onto it. This is done to make sure that the stack is never empty, which simplifies the logic in the next steps.

Next, we’ll iterate through the string and keep track of the length of the longest valid parentheses substring. Whenever we encounter an opening parentheses, we’ll push its index onto the stack. Whenever we encounter a closing parentheses, we’ll pop the top element from the stack. If the stack is empty after the pop, it means that we’ve encountered a closing parentheses that doesn’t have a corresponding opening parentheses, so we’ll push the current index onto the stack.

Finally, we’ll return the length of the longest valid parentheses substring.

Code

fun longestValidParentheses(s: String): Int {
    val stack = Stack<Int>()
    stack.push(-1)
    var maxLength = 0
    for (i in s.indices) {
        if (s[i] == '(') {
            stack.push(i)
        } else {
            stack.pop()
            if (stack.isEmpty()) {
                stack.push(i)
            } else {
                maxLength = max(maxLength, i - stack.peek())
            }
        }
    }
    return maxLength
}

Conclusion

In conclusion, finding the length of the longest valid parentheses substring is a classic problem in computer science that can be solved using a stack-based approach. By iterating through the string and using a stack to keep track of the indices of the parentheses characters, it’s possible to find the length of the longest valid parentheses substring in linear time.

Happy Coding!!!