3ms C solution, O(n) time, O(1) space


  • 0
    W
    int max(int a, int b) { return a > b ? a : b; }
    
    int longestValidParentheses(char* s) {
        char *t, *p;
        int open, ans = 0;
        
        open = 0;
        for (t=s, p=s; *t; t++) {
            *t == '(' ? open++ : open--;
            if (open == 0) {
                ans = max(ans, t-p+1);
            }else 
            if (open < 0) {
                open = 0;
                p = t + 1;
            }
        }
        
        open = 0;
        for (--t, p=t; *t; t--) {
            *t == ')' ? open++ : open--;
            if (open == 0) {
                ans = max(ans, p-t+1);
            }else 
            if (open < 0) {
                open = 0;
                p = t - 1;
            }
        }
        
        return ans;
    }
    

Log in to reply
 

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