32 Longest Valid Parentheses

1. Dynamic Programing

int longestValidParentheses(string s)
{
    vector<int> dp(s.size(), 0);
    int res = 0;
    for (int i = 1; i < s.size(); i++)
    {
        if (s[i] == ')')
        {
            if (i > 0 && s[i - 1] == '(')
            {
                if (i - 2 < 0)
                    dp[i] = 2;
                else
                    dp[i] = dp[i - 2] + 2;
            }
            else
            {
                if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(')
                {
                    dp[i] = dp[i - 1] + 2;
                    if (i - dp[i - 1] - 2 >= 0)
                    {
                        dp[i] += dp[i - dp[i - 1] - 2];
                    }
                }
            }
            res = max(res, dp[i]);
        }
    }
    return res;
}

Space	Time
$O(n)$	$O(n)$

2. Constant space solution

int longestValidParentheses(string s)
{
    int l = 0;
    int size = 0;
    int res = 0;
    // left to right
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == '(')
        {
            l++;
            size++;
        }
        else if (s[i] == ')')
        {
            l--;
            size++;
            if (l == 0)
            {
                res = max(size, res);
            }
            else if (l < 0)
            {
                l = 0;
                size = 0;
            }
        }
    }
    l = 0;
    size = 0;
    // right to left
    for (int i = s.size() - 1; i >= 0; i--)
    {
        if (s[i] == ')')
        {
            l++;
            size++;
        }
        else if (s[i] == '(')
        {
            l--;
            size++;
            if (l == 0)
            {
                res = max(size, res);
            }
            else if (l < 0)
            {
                l = 0;
                size = 0;
            }
        }
    }
    return res;
}

Space	Time
$O(1)$	$O(n)$