This solution is originally done by another person. It took me sometime to understand the code. I added some comments to make it easier to understand so people can save time, hopefully.

Here is the link https://leetcode.com/discuss/28694/my-o-n-ac-code-in-python?show=28694#q28694

```
class Solution:
# @param {string} s
# @return {integer}
# Dynamic Programming
def longestValidParentheses(self, s):
max_len = 0
#Use dictionary not list to reduce time
start_pos = {} # DP1 variable
stack = []
for i in range(len(s)):
if s[i] == '(':
stack.append(i)
else:
#Only the valid ')' has a chance to change max_len
if stack:
last = stack.pop()
start_pos[i] = last # DP2 State
#If the ')' right before '(' matching current valid '(' is also valid
if start_pos.has_key(last-1):
#Set start position of current ')' to the start position of the former ')'
start_pos[i] = start_pos[last - 1] # DP2 State
max_len = max(max_len, i - start_pos[i] + 1) #DP3 Transit
return max_len
```