Share my two-pass simple O(N) solution


  • 0
    O
    class Solution {
    public:
        int longestValidParentheses(string s) {
            int cnt(0), N = s.size();
            int cand1(0), cand2(0), ans = 0;
            for (int i = 0; i < N; i++) {
                if (cnt > 0 || s[i] == '(') cand1++;
                if (s[i] == ')' && cnt <= 0) {
                    cand1 = 0;
                    continue;
                }
                if (s[i] == '(') cnt++;
                else cnt--;
                if (cnt == 0) ans = max(cand1, ans);
            }
            cnt = 0;
            for (int i = N - 1; i >= 0; i--) {
                if (cnt > 0 || s[i] == ')') cand2++;
                if (s[i] == '(' && cnt <= 0) {
                    cand2 = 0;
                    continue;
                }
                if (s[i] == ')') cnt++;
                else cnt--;
                if (cnt == 0) ans = max(cand2, ans);
            }
            return ans;
        }
    };

Log in to reply
 

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