BinarySearch 0371 Multiple Parentheses

Problem statement

https://binarysearch.com/problems/Multiple-Parentheses/

Solution

Equal to Leetcode 0032. Longest Valid Parentheses.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, s):
        @lru_cache(None)
        def dp(i):
            if i == -1 or s[i] == "(": return 0
            if i >= 1 and s[i-1:i+1] == "()": return dp(i-2) + 2
            P = i - dp(i-1) - 1
            if P >= 0 and s[P] == "(":
                return dp(i-1) + dp(P-1) + 2
            return 0
            
        return max(dp(i) for i in range(len(s))) if s else 0