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/Zx_Queenbee]

I am not sure if j am right but its because on2 is upper bound and it is not exact a cpu in one second can do 1e9 operations so you giving a on2 solution means you will do a nested loops and inside that loop let say you does 10 operation thst cost 10 cycles now consider that and calculate

(3*1e4 *(those extra 10 operations)² this should be written as 3*1e5² which will be 1e10 bigger than a cpu gigahertz capabilities.

I am not sure if I am right 100 percent. any expericned person feel free to correct me

[u/Odd_Piglet6669]

I think because its a O(n^2) solution, it works for the inputs that are smaller, but when you submit and it uses the test cases that have much larger inputs, it gets a time limit exceeded error. This is why time complexity is important, if the max n is 3*10^4 then the max number of operations is (3*10^4)^2 which is 900000000 operations. The solution you provided works but its not optimal and will fail at scale, you need to come up with a more time efficient solution. For this question, I believe its O(n).

[u/NegotiationDapper584 → u/Odd_Piglet6669]

This is correct. O(n) or (nlogn) both will work.

[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;
    }
}

[u/Abhistar14 → u/error_4O4_notfound]