# My C++ 8ms O(n) space solution

• Well, the actual code is not long but I added the comments to illustrated the logics. The basic idea is to use a table to record maxlen of valid parentheses ending in every position, and keep filling the table with previous values.

``````int longestValidParentheses(string s) {
// t as a table, the i-th element represent the length of
// longest valid parentheses ending at position i
vector<int> t(s.size(),0);
int sz = s.size();
int mt = 0;
for (int i = 0;i < sz;i++) {
if (s[i] == ')' && i - 1 >= 0) {
if (s[i - 1] == '(') {
t[i] = 2;
if (i - t[i] >= 0) {
t[i] += t[i - t[i]];
}
}
else if(t[i-1]!=0 && i-1-t[i-1]>=0 && s[i-1-t[i-1]]=='(') {
t[i] = t[i-1] + 2;
if (i - t[i] >= 0 && t[i - t[i]]) {
// tracing back to merge previous valid length if
// they are continuous with present one
// s| ()(())		s| ()(())
// t| 020024   =>   t| 020026
//     |___|
// we need this look-up because the  increment of t[i] is
// made by left corresponding '('.Let's assume the '(' as in
// position j, then t[j] is 0 and give us no infomation about the
// parentheses lenth before it.
t[i] += t[i - t[i]];
}
}
mt = max(mt, t[i]);
}
}
return mt;
}``````

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