# Solution in C++ O(n)

• ``````class Solution
{
public:
int longestValidParentheses(string s)
{
int len = s.size(), maxLen = 0;
vector<int> iCount(len + 1, 0), leftCount(len + 1, 0);
for (int i = 0; i < len; ++i)
{
if (s[i] == '(')
{
leftCount[i + 1] = leftCount[i] + 1;
iCount[i + 1] = 0;
}
else
{
if (leftCount[i] > 0)
{
leftCount[i + 1] = leftCount[i] - 1;
if (s[i - 1] == '(') iCount[i + 1] = iCount[i - 1] + 2;
else iCount[i + 1] = iCount[i] + 2 + iCount[i - iCount[i] - 1];
}
}
maxLen = maxLen < iCount[i + 1] ? iCount[i + 1] : maxLen;
}
return maxLen;
}
};``````

• ``````class SolutionB
{
public:
int longestValidParentheses(string s)
{
int len = s.size(), maxLen = 0, validLeft = 0;
vector<int> iCount(len, 0);
for (int i = 0; i < len; ++i)
{
if ('(' == s[i]) ++validLeft;
else if (validLeft > 0)
{
--validLeft;
if ('(' == s[i - 1]) iCount[i] = iCount[i - 2] + 2;
else iCount[i] = iCount[i - 1] + 2 + iCount[i - 2 - iCount[i - 1]];
}
maxLen = iCount[i] > maxLen ? iCount[i] : maxLen;
}
return maxLen;
}
};``````

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