< 10 lines c++ DP solution using 6ms


  • 1
    1

    Very simple DP solution
    if s[i] == '(': g[i] = 0
    otherwise: g[i] is the length of longest substring ends at position i

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

Log in to reply
 

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