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
Top comments (0)