6ms C++ DP solution without using a stack


  • 0
    G
    class Solution {
    private:
    public:
        int longestValidParentheses(string s) {
            int n = (int)s.length();
            if (n < 2) return 0;
            int length[n] = {0}, max_len = 0; // length[i] is the maximum valid length with an ending index i
            for (int i = 0; i < n - 1;) {
                int l = i, r = i + 1;
                if (s[l] != '(' || s[r] != ')') {
                    ++i; continue;
                }
                do {
                    l -= length[l - 1]; // expand to the leftmost valid index
                    while (l > 0 && s[l - 1] == '(' && r + 1 < n && s[r + 1] == ')')
                        --l, ++r; // expand both ends
                } while (l > 0 && length[l - 1] > 0);
                max_len = max(max_len, length[r] = r - l + 1);
                i = r + 1;
            }
            return max_len;
        }
    };
    

Log in to reply
 

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