Python O(n) time, O(n) space solution with explanation

• 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.

Other examples:
`()(()` - 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)``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.