DP solution
class Solution:
def longestValidParentheses(self, s: str) -> int:
""" tc O(N) sc O(N)
dp[i]: longest ValidParentheses ending at ith idex
- only update dp when ) is encountered
- check every two consecutive characters
(1) s[i] == ) s[i-1] == ( then dp[i] = max(dp[i-2] +2,dp[i])
(2) s[i] == ), s[i-1] == ) : we check is substring before s[i-1] there exist a ( to pair with s[i]
"""
n = len(s)
res = 0
dp = [0]*n
for i in range(1,n):
if s[i] == ')':
if s[i-1] == '(':
dp[i] = (dp[i-2] if i >= 2 else 0) + 2
elif i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1] == '(':
dp[i] = dp[i-1] + (dp[i-dp[i-1]-2] if i-dp[i-1]-2 >= 0 else 0 ) +2
res = max(res,dp[i])
return res
class Solution:
def longestValidParentheses(self, s: str) -> int:
""" tc O(N) sc O(1)
main idea: left -> right and right -> left two rounds
1. with lcnt, rcnt left -> right: encounter (, lcnt +=1; encounter ), rcnt += 1 ; lcnt >= rcnt
2. when lcnt == rcnt, update max_len
"""
lcnt = rcnt = res = 0
for c in s:
if c == '(':
lcnt += 1
else:
rcnt += 1
if lcnt == rcnt:
res = max(res,2*rcnt)
elif rcnt > lcnt : # wn
lcnt = rcnt = 0
lcnt = rcnt = 0
for i in range(len(s)-1,-1,-1): # rcnt >= lcnt
c = s[i]
if c == ')':
rcnt += 1
else:
lcnt += 1
if lcnt == rcnt:
res = max(res,lcnt*2)
elif lcnt > rcnt :
lcnt = rcnt = 0
return res s