Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Longest valid parentheses challenge

Sharing is caring!

Problem statement
Given a string containing just the characters ( and ), find the length of the longest valid (well-formed) parentheses substring.

Sample input

(()

Sample output

2

Sample input 1

)()())

Sample output 1

4

Solution
We will solve this problem using a Stack. We are going to iterate over the input string s using an index i and push index i on the stack. While we iterate, we will check the letter positioned at the index contained on top of the stack (stack.peek()). If s[stack.peek()] is the letter ( and the current character is ) we will pop the top of the stack. We will keep popping as long as the later is true.

Once we iterated over all the letters in the input string the stack can either be empty or contain those indices for which we couldn’t find a counterpart parenthesis. For example, if we consider the input )()()), the stack will contain the index 0 and 5 at the end of the iteration.

In case the stack isn’t empty we will iterate over all indices contained in the stack and keep track of the maximum distance between two adjacent indices, since this distance represents the length of a valid (well-formed) parentheses substring. We then return the maximum distance.

In case the stack is empty, we know that the entire input string is a well-formed parentheses string and return the length of that string.

Full code

class Stack:
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[len(self.items)-1]

    def size(self):
        return len(self.items)

    def __str__(self):
        return ",".join([str(element) for element in self.items])
        
class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        
        ans = 0
        stack = Stack()
        i = 0
        while i < len(s):       
            while i < len(s) and s[i] == ')' and (not stack.isEmpty() and s[stack.peek()] == '('):
                stack.pop()                
                i += 1

            if i < len(s):                              
                stack.push(i)

            i += 1
                

        if stack.isEmpty():
            return len(s)

        b = len(s)
        while not stack.isEmpty():
            a = stack.pop()
            ans = max(ans, b - a - 1)
            b = a

        ans = max(ans, b)

        return ans
                
                 
def main():
    solution = Solution()
    print(solution.longestValidParentheses(")()())")) # 4
    print(solution.longestValidParentheses("(()")) # 2
    print(solution.longestValidParentheses("()")) # 2
    print(solution.longestValidParentheses("())")) # 2


if __name__ == "__main__": main()