My greedy solution - scan and reverse scan, 8ms


  • 1
    Z
    class Solution {
    public:
        int longestValidParentheses(string s) {
            int ans = 0, l = s.length(), sum = 0, start = 0;
            for (int i = 0; i < l; i++) {
                sum += (s[i] == '(')? 1 : -1;
                if (sum < 0) {
                    sum = 0;
                    start = i + 1;
                } else if (sum == 0) {
                    int len = i - start + 1;
                    if (ans < len) ans = len;
                }
            }
            start = l - 1;
            sum = 0;
            for (int i = l - 1; i >= 0; i--) {
                sum += (s[i] == '(')? 1 : -1;
                if (sum > 0) {
                    sum = 0;
                    start = i - 1;
                } else if (sum == 0) {
                    int len = start - i + 1;
                    if (ans < len) ans = len;
                }
            }
            return ans;
        }
    };

Log in to reply
 

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