Share my C O(N) simple solution (without using stack) with explanation


  • 0
    H

    I think it's a variant of maximum subarray problem. We can follow maximum subarray pattern to solve it.

    We can convert '(' to 1 and convert ')' to -1 then the problem becomes finding the longest subsequence which has sum equal to 0.

    But we need to consider the case '(((((()()' that the forward maximum subarray approach will fail to get correct answer.

    Fortunately, we can deal with such case by calculating from the end of string.

    int max(int a, int b) {
        return a > b ? a : b;
    }
    int longestValidParentheses(char* s) {
        int i, m = 0, count = 0, sum = 0;
        if (!s) {
            return 0;
        }
        for (i = 0; s[i]; ++i) {
            count++;
            sum += '(' == s[i] ? 1 : -1;
            if (0 == sum) {
                m = max(m, count);
            } else if (-1 == sum) {
                sum = 0;
                count = 0;
            }
        }
        sum = 0;
        count = 0;
        for (i = i - 1; i >= 0; --i) {
            count++;
            sum += '(' == s[i] ? -1 : 1;
            if (0 == sum) {
                m = max(m, count);
            } else if (-1 == sum) {
                sum = 0;
                count = 0;
            }
        }
        return m;
    }

Log in to reply
 

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