Longest valid parentheses using segment trees

longest_valid_parentheses.py

from collections import defaultdict

class Solution:
    def makeSeg(self, arr, i, j):
        seg = self.seg
        if (i, j) in seg:
            return seg[(i, j)]
        if i == j:
            seg[(i, j)] = arr[i]
            return arr[i]
        mid = (i + j) // 2
        curr = min(self.makeSeg(arr, i, mid), self.makeSeg(arr, mid + 1, j))
        seg[(i, j)] = curr
        return curr
    
    def getMin(self, i, j, ni, nj):
        seg = self.seg
        if ni >= i and nj <= j:
            return seg[(ni, nj)]
        if (ni < i and nj < i) or (ni > j and nj > j):
            return float('inf')
        mid = (ni + nj) // 2
        return min(self.getMin(i, j, ni, mid), self.getMin(i, j, mid + 1, nj))
    
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        ctr = 0
        freq = [ctr]
        for c in s:
            if c == '(':
                ctr += 1
            else:
                ctr -= 1
            freq.append(ctr)
        self.seg = {}
        self.makeSeg(freq, 0, n)
        exists = defaultdict(list)
        for i in range(n + 1):
            exists[freq[i]].append(i)
        mlen = 0
        for f in exists.values():
            k = len(f)
            for i in range(k):
                for j in range(i + 1, k):
                    if self.getMin(f[i], f[j], 0, n) - freq[f[i]] >= 0:
                        mlen = max(mlen, f[j] - f[i])
        return mlen