Longest Valid Parentheses

/*
Sliding Window (or by counting the open and close brackets)
Time Complexity : O(n) -> whole string will be traversed twice.
Space Complexity : O(1) -> Constant space will be used.
*/
class Solution {
    public int longestValidParentheses(String s) {
        if (s == null || s.length() <= 1) {
            return 0;
        }

        int open = 0;
        int close = 0;
        int maxLength = 0;

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                open++;
            } else {
                close++;
            }
            if (open == close) {
                maxLength = Math.max(maxLength, 2 * open);
            } else if (close > open) {
                open = 0;
                close = 0;
            }
        }

        open = 0;
        close = 0;

        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                open++;
            } else {
                close++;
            }
            if (open == close) {
                maxLength = Math.max(maxLength, 2 * open);
            } else if (open > close) {
                open = 0;
                close = 0;
            }
        }

        return maxLength;
    }
}

/*
Using stack.
Time Complexity : O(n) -> whole string will be traversed once.
Space Complexity : O(n) -> In worst case, size of the stack can grow upto length of the string (n).
*/
// class Solution {
//     public int longestValidParentheses(String s) {
//         if (s == null || s.length() <= 1) {
//             return 0;
//         }

//         Stack<Integer> stack = new Stack<>();
//         stack.push(-1);

//         int maxLength = 0;

//         for (int i = 0; i < s.length(); i++) {
//             if (s.charAt(i) == '(') {
//                 stack.push(i);
//             } else {
//                 stack.pop();
//                 if (stack.empty()) {
//                     stack.push(i);
//                 } else {
//                     maxLength = Math.max(maxLength, i - stack.peek());
//                 }
//             }
//         }

//         return maxLength;
//     }
// }

/*
Dynamic Programming
Time Complexity : O(n) -> whole string will be traversed once.
Space Complexity : O(n) -> Size of the DP array.
*/
// class Solution {
//     public int longestValidParentheses(String s) {
//         if (s == null || s.length() <= 1) {
//             return 0;
//         }

//         int[] dp = new int[s.length() + 1];
//         int maxLength = 0;

//         for (int i = 1; i < s.length(); i++) {
//             int dpIndex = i+1;
//             if (s.charAt(i) == ')') {
//                 if (s.charAt(i-1) == '(') {
//                     dp[dpIndex] = dp[dpIndex-2] + 2;
//                 } else if (i - dp[dpIndex-1] > 0 && s.charAt(i - dp[dpIndex-1] - 1) == '(') {
//                     dp[dpIndex] = dp[dpIndex - 1] + 2 + dp[dpIndex - dp[dpIndex-1] - 2];
//                 }
//                 maxLength = Math.max(maxLength, dp[dpIndex]);
//             }
//         }

//         return maxLength;
//     }
// }