Longest valid parantheses

#1

my code is giving me wrong ans help me to find out where i am wrong

question : https://leetcode.com/problems/longest-valid-parentheses/

#2

you code got accepted in leet code
for which input it is giving wrong output??

Your Code

class Solution {
public:
bool ValidParantheses(string s){

	stack<char> st;

	for (int i = 0; i < s.length(); i++)
	{
		char ch  = s[i];
		if(ch == '(' )
			st.push(ch);

		else if(!st.empty() && st.top() == '(')
			st.pop();

		else
			return false;
	}
	return st.empty();
}


    int longestValidParentheses(string s) {

	int ans = 0;
	for (int i = 0; i < s.length(); i++)
	{
		for (int j = i+2; j <= s.length(); j+=2)
		{
			if(ValidParantheses(s.substr(i,j)))
				ans = max(ans,j-i);
		}
	}
	return ans;
        
    }
};
#3

“)()())” for this input my code was giving me wrong ans and ur code is also giving error

#4

where you are running the code??
at leetcode??

#5

yes sir on leetcode it is giving reference error

#6

image
image1050×651 110 KB

code

#7

Screenshot (96)
Screenshot (96)1920×1080 279 KB

this code is just passing sample test see this carefully

#8

ohh
okay my bad
i think whole question is accepted
let me check your mistake now

#9

substr()
substr(i,length)
second argument is length of substring not the jth index
so correct statement is

       if(ValidParantheses(s.substr(i,j-i)))

                    ans = max(ans,j-i);

Modified Code

but this code will give TLE as it is brute force approach hence time complexity is very high
use dynamic programming to reduce time complexity

#10

ok thank you sir …yes sir it will give TLE but i have already optimized

#11

you have not done optimisations

use dp to reduce time complexity