Why O(n) solution TLE


  • 0
    W
    public int longestValidParentheses(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        Stack<Character> stack = new Stack<Character>();
        int len = 0, local = 0;
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(c);
            } else {
                if (!stack.empty()) {
                    stack.pop();
                    local += 2;
                    len = Math.max(len, local);
                } else { 
                    local = 0;
                }
            }
        }
        return len;
    }
    

    why there is a TLE error even though I am using a O(n) solution?


  • 0

    I submitted it several times, never got TLE but always Wrong Answer. Are you sure that's the code you submitted?


  • 0
    W

    yes, this is what I submitted, and I submitted 3 times yesterday, all get TLE, and I just tried it moment ago, still TLE, thank you for coming to my rescue, StefanPochmann, your solution is always inspiring btw.


  • 0
    Z

    take the case of ()((), your code will return 4 while it should be 2.


Log in to reply
 

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