*.py

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        best = 0
        cache = {}
        len_s = len(s)
        start_index = 0
        while start_index < len_s:
            curr = 0
            if start_index in cache:
                curr = cache[start_index]
                start_index += curr
            i = start_index
            while i < len_s:
                c = s[i]
                if c == '(':
                    curr += 1
                else:
                    curr -=1
                if curr < 0:
                    break
                if curr > len_s - i + 1:
                    print('start is {} i={} curr ={}'.format(start_index, i, curr))
                    while s[start_index] == '(':
                        start_index += 1
                    start_index -= 2
                    print('skipped to start_index={}'.format(start_index))
                    break
                if curr == 0:
                    # we've found the end of a valid set
                    curr_best = i - start_index
                    if curr_best > best:
                        best = curr_best + 1
                        cache[start_index] = best
                i += 1
            start_index += 1
        return best