FAANG Interview Question| Longest Valid Parentheses

#python #stack #programming

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

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 ')'.

Solution 1:

# O(n) time | O(n) space - where n is the length of the input string
def longestBalancedSubstring(string):
    stack = [-1]
    longest = 0
    for idx in range(len(string)):
        ch = string[idx]
        if ch == "(":
            stack.append(idx)
        else:
            stack.pop()
            if len(stack) == 0:
                stack.append(idx)
            else:
                top = stack[-1]
                longest = max(longest, idx - top)


    return longest

Better Solution

# O(n) time | O(1) space - where n is the length of the input string
def longestBalancedSubstring(string):
    return max(
            get_longest_sub_string_count(string, True),
            get_longest_sub_string_count(string, False)
        )

def get_longest_sub_string_count(string, left_to_right):
    open_ch= "(" if left_to_right else ")"
    step = 1 if left_to_right else -1
    idx = 0 if left_to_right else len(string) - 1
    open_count = 0
    close_count = 0
    longest = 0
    while idx > -1 and idx < len(string):
        ch = string[idx]
        if ch == open_ch:
            open_count +=1
        else:
            close_count += 1

        if close_count == open_count:
            longest = max(longest, open_count*2)
        elif close_count > open_count:
            open_count = 0
            close_count = 0

        idx += step


    return longest