# An O(n^2) Python Solution. Not super fast, but really easy to understand

• The basic idea is that every long valid sequence is expanded from short one(s). There are two ways of expansion: either by concatenation (e.g., "()" + "()" => "()()") or by enclosure (e.g., "("+ "()" + ")" = "(())"). So you start from all shortest sequences, i.e., "()", and try to merge them or expand them. The algorithm stops when you can no longer do either of these two operations with your current set of sequences. The longest sequence should be there already. Therefore, this solution not only gives the length of the longest sequence but also the sequence itself.

``````class Solution(object):
def longestValidParentheses(self, s):
stack = []
for i in range(0, len(s) - 1):
if s[i] == '(' and s[i + 1] == ')':
stack.append([i, i + 1])

dirty = True
while dirty:
dirty = False
nstack = []
# merge
for valid in stack:
if nstack:
last = nstack[-1]
if last[1] == valid[0] - 1:
last[1] = valid[1]
dirty = True
continue
nstack.append(valid)
stack = nstack
# expand
for valid in stack:
if valid[0] > 0 and valid[1] < len(s) - 1:
if s[valid[0] - 1] == '(' and s[valid[1] + 1] == ')':
valid[0] -= 1
valid[1] += 1
dirty = True
record = 0
for start, end in stack:
record = max(record, end - start + 1)
return record``````

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