Central idea is to be able to extend valid parentheses, like
()() notice that the second
() extends the previous valid parenthesis to give a length of 4.
()(() - in this case, longest valid is 2, but the moment we add another parentheses at the end
()(()), the whole string becomes a valid parentheses, so it is important to remember at
i = 2 that there was a valid parentheses that ended just before it, so if a valid parentheses is created using
i=2 as the starting point (opening parenthesis), the previous length can be added to it.
For this, we can use an array (I call this array
LengthEndingAtIndex as it stores the length of valid parenthesis ending at every offset. Whenever I find a valid parentheses (using a stack), I just store the current valid length into this array.
Please let me know if any part is not clear, beginner here.
class Solution(object): def longestValidParentheses(self, s): """ :type s: str :rtype: int """ stack =  maxLen = 0 currentRun = 0 LengthEndingAtIndex = [0 for i in range(0, len(s)+1)] for i in range(0, len(s)): if len(stack) == 0: if s[i] == '(': stack.append((i, s[i])) continue topOfStackIndex, topOfStackParenthesis = stack[-1] if s[i] == ')': if topOfStackParenthesis == '(': stack = stack[0:-1] currentRun = (i - topOfStackIndex + 1) + LengthEndingAtIndex[topOfStackIndex] maxLen = max(currentRun, maxLen) LengthEndingAtIndex[i+1] = currentRun continue else: stack.append((i, s[i])) return max(LengthEndingAtIndex)