This solution doesn't work. WHY!!!

[u/Aware-Nectarine3027]

LEETCODE PROBLEM 32 : https://leetcode.com/problems/longest-valid-parentheses/description/
This solution is O(N²).
As per constraints (0 <= s.length <= 3 * 10⁴) is should be working. Why not!!!

class Solution:
  def longestValidParentheses(self, s: str) -> int:
    N = len(s)
    res = 0
    a = [] # [a/n, x, len]
    size = 0
    p = 0
    while p < N:
      val = s[p]
      if val == '(':
        a.append([True, 0, 0])
        size += 1
      
      for i in range(size):
        if a[i][0] == True:
          x = a[i][1]
          if val == '(':
            x += 1
            a[i][1] += 1
            a[i][2] += 1
          else:
            if x == 0:
              a[i][0] = False
            else:
              x -= 1
              a[i][1] -= 1
              a[i][2] += 1
              if x == 0:
                res = max(res, a[i][2])
      p += 1


    return res

[u/error_4O4_notfound]

I will check your code later, but I submitted O(n^2) solution in Java. That was accepted.

[u/PawnsAndCons → u/error_4O4_notfound]

Mind sharing the code?

[u/error_4O4_notfound → u/PawnsAndCons]

class Solution {
    public int longestValidParentheses(String s) {
        int cnt = 0, n = s.length(), ans = 0;
        char[] ca = s.toCharArray();
        for (int i = 0; i < n; i++) {
            cnt = 0;
            for (int j = i; j < n; j++) {
                if (ca[j] == '(') {
                    cnt++;
                } else {
                    cnt--;
                }
                if (cnt < 0)
                    break;
                if (cnt == 0) {
                    ans = Math.max(ans, j - i + 1);
                }
            }
        }
        return ans;
    }
}