I'm stuckling a test case


#1

Hello everybody. I’m stuckling in test:
A: ")()))(())((())))))())()(((((())())((()())(())((((())))())((()()))(()(((()()(()((()()))(())()))((("
for which correct answer is 30.
My answer is 80. So i modified my solution in such way that it gives path now (indexes of longest correct substring).
I have checked this output and have seen all indexes different and coresponding substring really has length 80 and forms correct parentheses. Can anybody give me help, please! and if i am right then i damand to reset my timer and change this test case.


#2

Hi, I’m stuck at same test case. Is the answer 30 right answer? I’m getting answer 94. Removing last 3 characters, in remaining string has equal number of ‘(’ and ‘)’ . Can you help with this test case?


#3

“)()))(())((())))))())()(((((())())((()())(())((((())))())((()()))(()(((()()(()((()()))(())()))” string is not well formed. I got my mistake.


#4

Hi , im getting the exact same error. Can you tell me the mistake im making


#5

Hi, I don’t remember what was wrong. If you check every n * (n + 1) / 2 substring to be well formed you will get answer. Can you check this with O(n^2) time complexity. And finally, can you reduce the time complexity to linear?


#6

hey ! i found the error you are misunderstanding it as sum of all valids but we are asked a substring therefore the longest valid continuation actually


#7
//I was not checking if there are '(' left after complete traversal of the string for this sol:
int Solution::longestValidParentheses(string A) {
    stack<char> stk;
    int i = 0, sol = 0, temp = 0This text will be hidden;
    while(i < A.length()) {
        if(A[i] == '(') stk.push('(');
        else {
            if(stk.empty() == true) temp = 0;
            else {
                temp += 2;
                stk.pop();
                sol = max(sol, temp);
            }
        }
        ++i;
    }
    return sol;
}

//fix for this:
    int Solution::longestValidParentheses(string A) {
        stack<int> stk;
        int i = 0, sol = 0, temp = 0;
        while(i < A.length()) {
            if(A[i] == '(') {
                stk.push(temp);
                temp = 0;
            }
            else {
                if(stk.empty() == true) temp = 0;
                else {
                    temp += stk.top() + 2;
                    stk.pop();
                    sol = max(sol, temp);
                }
            }
            ++i;
        }
        return sol;
    }

#8

Great work bro. I was stuck at this test case for so long. So the mistake that we were doing is -
Take the string
“()(((((())())((()())(())((((())))())((()()))(()(((()()(()((()()))(())()))(((”
The expected output for this is 30. This is a substring of the above test case and which actually matters.
After the first couple of parentheses till n-3, we’ve more ‘(’ then ‘)’ so in effect we’ll have to drop off third and fourth char which is ‘(’ so it makes it non contiguous with the first couple but most probably your soln won’t be taking this into account.