There may be an edge case which might be missing, kindly analyse it once again, you'll find it. If you like our efforts, will you like to write a review about us here - g.page/Pepcoding/review?rc
Use this code it is only 5% percent faster but passes all the test cases....... class Solution: def removeInvalidParentheses(self, s: str) -> List[str]: def removals(s,stack): for i in s: if(i=="("): stack.append(i) elif(i==")"): if(len(stack)==0 or stack[-1]==")"): stack.append(i) else: stack.pop() return stack
for i in range(len(s)): if(s[i]==rmarr[idx]): if(i==0): recursion(s[:i]+s[i+1:],rmarr,idx+1) else: if(s[i]!=s[i-1]): recursion(s[:i]+s[i+1:],rmarr,idx+1)
TLE can be resolved if we pass another HashSet object in the recursive function to track if the string has been visited before. If the string is visited,simply return. otherwise, put the string in HashSet and then perform rest of the operation. :Just add following condition at the very first line of recursive function. if(visited.contains(s)) return; add value into "visited" structure right before the For loop.
Here is the code for reference. public static void solution(String s, int maxRemovalAllowed, Set ans, Set visited ) { if(visited.contains(s)) return; visited.add(s); if(maxRemovalAllowed == 0) { if(getInvalidParentheses(s) == 0) { ans.add(s); } return; } for(int i = 0; i< s.length() ; i++) { String left = s.substring(0,i); String right = s.substring(i+1); solution(left+right, maxRemovalAllowed-1,ans,visited); } }
For Those getting TLE exception , just add a check in method to not visit same string twice as below and it will pass : void getValids(String s, Set set, int mr){ if(visited.contains(s)) return; visited.add(s); if( mr == 0 ) { int now = getMinRemoval(s); if( now == 0){ set.add(s); } return; }
for( int i = 0 ; i < s.length() ; i++){ if(Character.isLetter(s.charAt(i))) continue; String left = s.substring(0, i); String right = s.substring(i+1); getValids(left+right, set, mr-1); } }
Thanks for the Video and the explanation. Just to add you can also modify the getMin() to calculate min without a stack as follows - private int getMin(String s) { int left =0; int right = 0; for (int i=0;i 0) left--; else right++; } } return left+right; }
For TLE leetcode just add a check if the set contains the string as Visited set. private void removeUtil(String s, int mr, List ans, HashSet set) { if(set.contains(s)) { return; } set.add(s); if(mr == 0 && getMin(s) == 0) { ans.add(s); } for(int i=0; i
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem. If you like our efforts, we request a review g.page/Pepcoding/review?rc You can subscribe to our channel here czcams.com/users/Pepcodingabout?view_as=subscriber
Sir ji- sab kuchh bhool jaye, chahe Gajani ban jaye, but str.subtring(0, i) and str.substring(i+1) kabhi nahi bhool sakta. Aap har question me substring() pe itna zor lagate ho.Thanks another great video.
Glad you think so! and If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Great explanation! Cheers. But this is not exactly Leetcode 301. Out there the input can have the alphabets as well. Example input: "(a)())()" Output: "(a)()()", "(a())()"
Continuing the above discussion: s = "(a)())()" The modification in the getMin function is as follows [Python]: def getMin(self, s): stack = [] for i in s: if i == "(": stack.append(i) elif i == ")": if stack and stack[-1] == '(': stack.pop() else: stack.append(i) return len(stack) But it will give TLE for # s = "((()((s((((()". An optimization is needed which is discussed in other comments.
class Solution: def removeInvalidParentheses(self, s):
level = {s} print(level) while True: valid = [] for elem in level: print(elem) if self.isValid(elem): valid.append(elem) if valid: return valid # initialize an empty set new_level = set() # BFS for elem in level: for i in range(len(elem)): new_level.add(elem[:i] + elem[i + 1:]) level = new_level def isValid(self,s): count = 0 for c in s: if c == '(': count += 1 elif c == ')': count -= 1 if count < 0: return False return count == 0
Thank you so much and If you like the content could you post something on LinkedIn about us? This will help us in reaching out to more people and help a lot of other students as well Something like this Sumeet Malik from Pepcoding is making all his content freely available to the community You can check it out here - www.pepcoding.com/resources / Also, this is the youtube channel - czcams.com/users/Pepcodingplaylists?view_as=subscriber
Glad to know that you liked the content and thank you for appreciating. The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos. So, keep motivating, keep learning and keep loving Pepcoding😊
Got TLE on leetcode for this solution here is the updated code public List removeInvalidParentheses(String s) { List ls=new ArrayList(); int minRemoval=getMinRemovals(s); HashMap set=new HashMap(); getValidAns(s,set,ls,minRemoval); return ls; } public void getValidAns(String s, HashMap set, List ls,int minRemoval){ if(minRemoval==0){ if(getMinRemovals(s)==0){ ls.add(s); } return; } for(int i=0;i
If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Great explanation sir ! Sir, isn't it becoming too much complex by removing any random "mra" brackets from the string and then again checking if its valid in the base case and then checking if the string exists ? If instead we remove the same type of bracket before it, I think it will become too much optimized, as it will make the correct strings only.
Thankyou beta! I am glad you liked it. I also hope that you are watching till the end and trying to understand the what, how, and especially why of the problem. If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )
Leetcode 301 (JAVA SOLUTION - Invalid parentheses) class Solution { public List removeInvalidParentheses(String str) { List ans = new ArrayList(); HashSet hash = new HashSet(); int min_removal = getMin(str); solution(str, min_removal, hash, ans); return ans; }
public static void solution(String str, int min_removal_allowed, HashSet hash, List ans){ if(hash.contains(str)){ return; }
hash.add(str);
if(min_removal_allowed == 0){ int mrn = getMin(str); // min removal now if(mrn == 0){
Solution works , but I can't understand ,how? You are not handling alphabets , but still it is getting accepted, how? Do we not need to worry about the alphabets? Please explain🙏
Leetcode 301: Python solution class Solution: def removeInvalidParentheses(self, s: str) -> List[str]: ans = set() mra = self.getMin(s) self.solution(s, mra, ans, set()) return list(ans) def solution(self, s, mra, ans, visited): if s in visited: return visited.add(s) if mra == 0: mrnow = self.getMin(s) if mrnow == 0: if s not in ans: ans.add(s) return for i in range(len(s)): left = s[0:i] right = s[i+1:] self.solution(left+right, mra-1, ans, visited) def getMin(self, s): stack = [] for i in s: if i == "(": stack.append(i) elif i == ")": if stack and stack[-1] == '(': stack.pop() else: stack.append(i) return len(stack) # "((()((s((((()"
The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos. So, keep motivating and Keep loving😊
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem. If you like our efforts, we request a review g.page/Pepcoding/review?rc You can subscribe to our channel here czcams.com/users/Pepcodingabout?view_as=subscriber For clearing your doubts, you can join our community on telegram t.me/pepcoding
One Flaw found in the solution: We are removing the character immediately but we also need to keep it and start looking from the next index here is my Python3 code accepted on Leetcode class Solution: def removeInvalidParentheses(self, s: str) -> List[str]: ''' To find Minimum number of characters ''' def findMin(s): st = [] for i in s: if i not in ["(", ")"]: continue if not st: st.append(i) else: if i == ")" and st[-1] == "(": st.pop() else: st.append(i) return len(st) def helper(start_idx, remaining, mask): if remaining == 0: found_str = ''.join([s[i] for i in range(len(mask)) if mask[i] == 1]) # Checking if found string is valid or not if findMin(found_str) == 0: ans.add(found_str) return if start_idx == len(s): return ''' 2 choices remove that character or not Remove -> mask[] = 0 and remaining - 1 Keep -> mask[] = 1 In both cases we advance start_idx by 1 ''' # Skipping characters other than '(' and')' if s[start_idx] in [')', '(']: mask[start_idx] = 0 helper(start_idx + 1, remaining - 1, mask) mask[start_idx] = 1 helper(start_idx + 1, remaining, mask) ans = set() invalid_count = findMin(s) helper(0, invalid_count, [1 for _ in range(len(s))]) return list(ans)
for removing tle try to use set for checking each and very string wheteher it is valid or not Here is The Code: class Solution { public: string str; vector ans; int clen; // checking the bool isValid(string s) { stack st; int f=1; for(int i=0;s[i];i++) { if(s[i]=='(') st.push(s[i]); else if(s[i]==')') { if(!st.empty()) { if(st.top()=='(') { st.pop(); } else { f=0; break;
Hi, I tried solving this on Leetcode but after 93 test cases it says time limit exceeded. I followed the same approach as explained in the video. Please do advice what can be done. I can share the code if needed. Thanks
class Solution: def removeInvalidParentheses(self, s):
level = {s} print(level) while True: valid = [] for elem in level: print(elem) if self.isValid(elem): valid.append(elem) if valid: return valid # initialize an empty set new_level = set() # BFS for elem in level: for i in range(len(elem)): new_level.add(elem[:i] + elem[i + 1:]) level = new_level def isValid(self,s): count = 0 for c in s: if c == '(': count += 1 elif c == ')': count -= 1 if count < 0: return False return count == 0
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem. If you like my efforts, I request a review g.page/Pepcoding/review?rc
If anyone is looking for leetcode solution for the same. class Solution:
def backTrack(self, curr , ans, minRemove,visited ): if minRemove == 0 : if self.minPR(curr) == 0: ans.add(curr) return for i in range(len(curr)): if curr[i] not in [ '(',')']: continue l = curr[0:i]+curr[i+1:] if not l in visited : visited.add(l) self.backTrack(curr[0:i]+curr[i+1:],ans,minRemove-1, visited) def minPR(self, s ): left,right = 0,0 for par in s: if par == '(': left += 1 elif par == ')': if left == 0 : right += 1 else: left -= 1 return right+left def removeInvalidParentheses(self, s: str) -> List[str]: ans = set() visited = set() self.backTrack(s,ans, self.minPR(s),visited)
Glad to know that you like our explanation. Visit - nados.pepcoding.com and sign up to NADOS. For structured content and better experience. Don't forget to follow us on Instagram instagram.com/pepcoding/
To get out from out of memory error, Keep a visited hashset to keep track of each string traversed so far if it is already traversed return. if(visited.contains(str)){ return; } visited.add(str);
sir, isme aapne backtrack to kiya hi nhi. jab ek elment hata kar call lagai, uske baad wo normal ho sake, taaki wo dusri call laga sake, (yeh to aapne kiya hi nhi).
Thankyou beta! I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem. If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
cpp solution without tle::: i have done an optimisation to cut down rechecking of similar subproblem by using a map. class Solution { public: vector ans; unordered_map map; int get_min(string s) { stack st; for (int i = 0; i < s.size(); i++) { if (s[i] == '(')st.push('('); else if (s[i] == ')') { if (st.size()) { if (st.top() == '(') { st.pop(); } else { st.push(')'); } } else { st.push(')'); } } } return st.size(); } void solve2(string s,int minimum_removal_allowed) { if(map[s]!=0)//for checking that string is already exist in map or not return; else map[s]++; if(minimum_removal_allowed==0) { int minimum_removal_now=get_min(s); if(minimum_removal_now==0) { ans.push_back(s); } return; } for(int i=0;i
Beta, I regret to inform you that, I won't be able to answer/solve the personal doubts of each and every student over here. For clearing your doubts, you can join our community on telegram - t.me/pepcoding.
Beta, I regret to inform you that, I won't be able to answer/solve the personal doubts of each and every student over here. For clearing your doubts, you can join our community on telegram - t.me/pepcoding.
The way it is explained, its amazing, one can understand how to approach solution. Thanks for the video.
Great explanation, @Pepcoding you can add time and space complexity as well in the video for more details.
Nicely explained. Thank you. But, the runtime is quite high. It exceeds the time limit on Leetcode.
There may be an edge case which might be missing, kindly analyse it once again, you'll find it. If you like our efforts, will you like to write a review about us here - g.page/Pepcoding/review?rc
Happened with me too. I tried running it on Jupyter notebook and it works just fine but the time taken is horrendous
Use this code
it is only 5% percent faster but passes all the test cases.......
class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
def removals(s,stack):
for i in s:
if(i=="("):
stack.append(i)
elif(i==")"):
if(len(stack)==0 or stack[-1]==")"):
stack.append(i)
else:
stack.pop()
return stack
rmarr=removals(s,[])
ans=[]
def recursion(s,rmarr,idx):
if(idx==len(rmarr)):
if(len(removals(s,[]))==0):
ans.append(s)
return
for i in range(len(s)):
if(s[i]==rmarr[idx]):
if(i==0):
recursion(s[:i]+s[i+1:],rmarr,idx+1)
else:
if(s[i]!=s[i-1]):
recursion(s[:i]+s[i+1:],rmarr,idx+1)
recursion(s,rmarr,0)
if(len(ans)==0):
ans=[""]
return set(ans)
TLE can be resolved if we pass another HashSet object in the recursive function to track if the string has been visited before. If the string is visited,simply return. otherwise, put the string in HashSet and then perform rest of the operation. :Just add following condition at the very first line of recursive function.
if(visited.contains(s))
return;
add value into "visited" structure right before the For loop.
Here is the code for reference.
public static void solution(String s, int maxRemovalAllowed, Set ans, Set visited ) {
if(visited.contains(s))
return;
visited.add(s);
if(maxRemovalAllowed == 0) {
if(getInvalidParentheses(s) == 0) {
ans.add(s);
}
return;
}
for(int i = 0; i< s.length() ; i++) {
String left = s.substring(0,i);
String right = s.substring(i+1);
solution(left+right, maxRemovalAllowed-1,ans,visited);
}
}
Thank u bruh😍😍
Sir this code gives TLE on platform (C++)
I used same approach and it got submitted on leetcode.
For Those getting TLE exception , just add a check in method to not visit same string twice as below and it will pass :
void getValids(String s, Set set, int mr){
if(visited.contains(s)) return;
visited.add(s);
if( mr == 0 ) {
int now = getMinRemoval(s);
if( now == 0){
set.add(s);
}
return;
}
for( int i = 0 ; i < s.length() ; i++){
if(Character.isLetter(s.charAt(i))) continue;
String left = s.substring(0, i);
String right = s.substring(i+1);
getValids(left+right, set, mr-1);
}
}
still we are getting same TLE error , last expected input ")(((()(y((u()(z()()"
thamks vro
Sir it amazing I like your teaching style thanks sir I have watched all level1 vedio and now I am here..
Thanks for the Video and the explanation. Just to add you can also modify the getMin() to calculate min without a stack as follows -
private int getMin(String s) {
int left =0;
int right = 0;
for (int i=0;i 0) left--;
else right++;
}
}
return left+right;
}
this will not work.
It's working
Sir if possible try to upload atleast 5 videos a day..It would be a great help to us. Loving these videos🔥
beta kal 5 aai thi. aj bhi aaengi
Tried this solution, it works on IDE but leetcode shall give TLE.
Dp solution will not give tle
For TLE leetcode just add a check if the set contains the string as Visited set.
private void removeUtil(String s, int mr, List ans, HashSet set) {
if(set.contains(s)) {
return;
}
set.add(s);
if(mr == 0 && getMin(s) == 0) {
ans.add(s);
}
for(int i=0; i
Your backtracing algorithm approach is one of the best
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
If you like our efforts, we request a review
g.page/Pepcoding/review?rc
You can subscribe to our channel here
czcams.com/users/Pepcodingabout?view_as=subscriber
Sir ji- sab kuchh bhool jaye, chahe Gajani ban jaye, but str.subtring(0, i) and str.substring(i+1) kabhi nahi bhool sakta. Aap har question me substring() pe itna zor lagate ho.Thanks another great video.
Haha..
Keep watching and keep learning😊🙏
The Best Explanation...Even A Very Beginner Can Understand it.
Glad you think so! and If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Sir, you are doing a great job. Thank you!
So nice of you. keep motivating, keep learning and keep loving Pepcoding😊
Nice explanation.
Great video sir.
Great explanation! Cheers.
But this is not exactly Leetcode 301. Out there the input can have the alphabets as well.
Example input: "(a)())()" Output: "(a)()()", "(a())()"
Alright, noted.
same
Continuing the above discussion:
s = "(a)())()"
The modification in the getMin function is as follows [Python]:
def getMin(self, s):
stack = []
for i in s:
if i == "(":
stack.append(i)
elif i == ")":
if stack and stack[-1] == '(':
stack.pop()
else:
stack.append(i)
return len(stack)
But it will give TLE for # s = "((()((s((((()". An optimization is needed which is discussed in other comments.
Please discuss the BFS approach too .
class Solution:
def removeInvalidParentheses(self, s):
level = {s}
print(level)
while True:
valid = []
for elem in level:
print(elem)
if self.isValid(elem):
valid.append(elem)
if valid:
return valid
# initialize an empty set
new_level = set()
# BFS
for elem in level:
for i in range(len(elem)):
new_level.add(elem[:i] + elem[i + 1:])
level = new_level
def isValid(self,s):
count = 0
for c in s:
if c == '(':
count += 1
elif c == ')':
count -= 1
if count < 0:
return False
return count == 0
Lol muje bhi height ki spelling 30 saal mai yaad hui hai ... awesome channel, awesome content.
Thank you so much and If you like the content could you post something on LinkedIn about us? This will help us in reaching out to more people and help a lot of other students as well
Something like this
Sumeet Malik from Pepcoding is making all his content freely available to the community
You can check it out here - www.pepcoding.com/resources
/
Also, this is the youtube channel - czcams.com/users/Pepcodingplaylists?view_as=subscriber
We can add irrespective if answer is present is hashset or not because hashset will take care of duplicates by default
Amazing content!!
Glad you enjoyed it
one of the most iconic lines by sumeet sir : "chala chala sa lag raha hai " .
Edit : Great explanation sir .
Glad to know that you liked the content and thank you for appreciating.
The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos.
So, keep motivating, keep learning and keep loving Pepcoding😊
My life summed up at 10:14
Got TLE on leetcode for this solution
here is the updated code
public List removeInvalidParentheses(String s) {
List ls=new ArrayList();
int minRemoval=getMinRemovals(s);
HashMap set=new HashMap();
getValidAns(s,set,ls,minRemoval);
return ls;
}
public void getValidAns(String s, HashMap set, List ls,int minRemoval){
if(minRemoval==0){
if(getMinRemovals(s)==0){
ls.add(s);
}
return;
}
for(int i=0;i
Salute you, sir, for great content!
If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Great explanation sir !
Sir, isn't it becoming too much complex by removing any random "mra" brackets from the string and then again checking if its valid in the base case and then checking if the string exists ? If instead we remove the same type of bracket before it, I think it will become too much optimized, as it will make the correct strings only.
Can please elaborate your idea??
Very well explained!!
Thankyou beta!
I am glad you liked it. I also hope that you are watching till the end and trying to understand the what, how, and especially why of the problem. If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )
Sir hum isko is way me kr skte hain? jaise har recursive call me hum current index i include(not remove,k) or not include(remove,k-1)??
i tried the code in leetcode and it showed time limit exceed. will someone help?
Leetcode 301 (JAVA SOLUTION - Invalid parentheses)
class Solution {
public List removeInvalidParentheses(String str) {
List ans = new ArrayList();
HashSet hash = new HashSet();
int min_removal = getMin(str);
solution(str, min_removal, hash, ans);
return ans;
}
public static void solution(String str, int min_removal_allowed, HashSet hash, List ans){
if(hash.contains(str)){
return;
}
hash.add(str);
if(min_removal_allowed == 0){
int mrn = getMin(str); // min removal now
if(mrn == 0){
ans.add(str);
}
return;
}
for(int i = 0; i
Solution works , but I can't understand ,how? You are not handling alphabets , but still it is getting accepted, how? Do we not need to worry about the alphabets? Please explain🙏
20:49 if someone missed it , here is how the isValid() method was defined. 😂
Leetcode 301: Python solution
class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
ans = set()
mra = self.getMin(s)
self.solution(s, mra, ans, set())
return list(ans)
def solution(self, s, mra, ans, visited):
if s in visited:
return
visited.add(s)
if mra == 0:
mrnow = self.getMin(s)
if mrnow == 0:
if s not in ans:
ans.add(s)
return
for i in range(len(s)):
left = s[0:i]
right = s[i+1:]
self.solution(left+right, mra-1, ans, visited)
def getMin(self, s):
stack = []
for i in s:
if i == "(":
stack.append(i)
elif i == ")":
if stack and stack[-1] == '(':
stack.pop()
else:
stack.append(i)
return len(stack)
# "((()((s((((()"
Sir ek hi dil hai kitni baar jeetoge ❤️
haha
bhiya iska koi optimised solution h kya ..kyuki agar worst case le hum to ye 11 length se upar wali string ke liye TLE de rha h
thanks for the soln and explaination sir . I just want to ask whats the time complexity of the soln ?
Very well explained
sir aap kha se padhe ye sab. just mind blowing . already completed your recursion video. im in NIT bhopal but your are better than out professor. :)
The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos.
So, keep motivating and Keep loving😊
Great teacher
Glad you think so!
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
If you like our efforts, we request a review
g.page/Pepcoding/review?rc
You can subscribe to our channel here
czcams.com/users/Pepcodingabout?view_as=subscriber
For clearing your doubts, you can join our community on telegram
t.me/pepcoding
One Flaw found in the solution:
We are removing the character immediately but we also need to keep it and start looking from the next index
here is my Python3 code accepted on Leetcode
class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
'''
To find Minimum number of characters
'''
def findMin(s):
st = []
for i in s:
if i not in ["(", ")"]: continue
if not st:
st.append(i)
else:
if i == ")" and st[-1] == "(":
st.pop()
else:
st.append(i)
return len(st)
def helper(start_idx, remaining, mask):
if remaining == 0:
found_str = ''.join([s[i] for i in range(len(mask)) if mask[i] == 1])
# Checking if found string is valid or not
if findMin(found_str) == 0:
ans.add(found_str)
return
if start_idx == len(s):
return
'''
2 choices remove that character or not
Remove -> mask[] = 0 and remaining - 1
Keep -> mask[] = 1
In both cases we advance start_idx by 1
'''
# Skipping characters other than '(' and')'
if s[start_idx] in [')', '(']:
mask[start_idx] = 0
helper(start_idx + 1, remaining - 1, mask)
mask[start_idx] = 1
helper(start_idx + 1, remaining, mask)
ans = set()
invalid_count = findMin(s)
helper(0, invalid_count, [1 for _ in range(len(s))])
return list(ans)
sir this solution is giving TLE on leetcode
Ok ji. I will check
Yes true.
yes, TLE
for removing tle try to use set
for checking each and very string wheteher it is valid or not
Here is The Code:
class Solution {
public:
string str;
vector ans;
int clen;
// checking the
bool isValid(string s)
{
stack st;
int f=1;
for(int i=0;s[i];i++)
{
if(s[i]=='(')
st.push(s[i]);
else if(s[i]==')')
{
if(!st.empty())
{
if(st.top()=='(')
{
st.pop();
}
else
{
f=0;
break;
}
}
else
{
f=0;
break;
}
}
}
if(f==1 && st.size()==0)
return true;
else
return false;
}
set se;
void all(int k,int i,string bw)
{
if(k==0 && bw.size()==clen)
{
// if string is repeated then neglect it
if(se.find(bw)!=se.end())
return;
else
se.insert(bw);
//cout
Great explanation sir!
one suggestion please include the time complexity analysis of the algorithm.
Hanji, I am missing out on an important thing. Bhool ja rha hun. Karunga isse aage ki videos mei
One optimization - no need to check for valid string if it’s already in set.
very nice explaination!
Glad you liked it!
nice sir but
giving TLE for long strings leetcode 301
public class RemoveInvalidParenthesis {
private static int getMin(String str) {
Stack st=new Stack();
for(int i=0;i
how about space complexity is it N {for stack } how much for internal stack {used for recursive calls } is it N ??
Hi, I tried solving this on Leetcode but after 93 test cases it says time limit exceeded. I followed the same approach as explained in the video. Please do advice what can be done. I can share the code if needed. Thanks
class Solution:
def removeInvalidParentheses(self, s):
level = {s}
print(level)
while True:
valid = []
for elem in level:
print(elem)
if self.isValid(elem):
valid.append(elem)
if valid:
return valid
# initialize an empty set
new_level = set()
# BFS
for elem in level:
for i in range(len(elem)):
new_level.add(elem[:i] + elem[i + 1:])
level = new_level
def isValid(self,s):
count = 0
for c in s:
if c == '(':
count += 1
elif c == ')':
count -= 1
if count < 0:
return False
return count == 0
this is giving TLE , update your answer
Mazaa aaya bhai....awesome
For better eperience visit on nados.pepcoding.com
Also follow us on our Instagram account to stay tuned.
instagram.com/pepcoding/
Great explanation sir
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
If you like my efforts, I request a review
g.page/Pepcoding/review?rc
Sir please come back😭😭
Great.. But whats the time complexity of this?
If anyone is looking for leetcode solution for the same.
class Solution:
def backTrack(self, curr , ans, minRemove,visited ):
if minRemove == 0 :
if self.minPR(curr) == 0:
ans.add(curr)
return
for i in range(len(curr)):
if curr[i] not in [ '(',')']: continue
l = curr[0:i]+curr[i+1:]
if not l in visited :
visited.add(l)
self.backTrack(curr[0:i]+curr[i+1:],ans,minRemove-1, visited)
def minPR(self, s ):
left,right = 0,0
for par in s:
if par == '(':
left += 1
elif par == ')':
if left == 0 :
right += 1
else:
left -= 1
return right+left
def removeInvalidParentheses(self, s: str) -> List[str]:
ans = set()
visited = set()
self.backTrack(s,ans, self.minPR(s),visited)
return ans if ans else [""]
maza aagaya :)
i think we can use memoziation approch also
Sir foundation ke baad koi book follow kr sakte hai any suggestion?
yar book se kahin acha hai, aap leetcode, codechef, codeforces karein. ye practical sa kaam hai. books are inferior to actually solving problems
loved it sir...
Please like share and subscribe as well.
getting TLE on leetcode using same code, can anyone help me.
Great content
please share and subscribe
Good explanation, but not the most optimized solution. Getting TLE on leetcode
Glad to know that you like our explanation.
Visit - nados.pepcoding.com and sign up to NADOS.
For structured content and better experience.
Don't forget to follow us on Instagram instagram.com/pepcoding/
your solutionis giving tle on leetcode
leetcode ki alag playlist bna rhe hain yar.
To get out from out of memory error, Keep a visited hashset to keep track of each string traversed so far if it is already traversed return.
if(visited.contains(str)){
return;
}
visited.add(str);
Thank you Alankruthi.
sir, isme aapne backtrack to kiya hi nhi.
jab ek elment hata kar call lagai, uske baad wo normal ho sake, taaki wo dusri call laga sake, (yeh to aapne kiya hi nhi).
just find opening and closing bracket count and if (>) then (-) if )>( then )-(
what is it's time complexity?
Excellent!
Thank you! Cheers!
sir bs video me ek chiz ki kami hai ki app hmesha complexity ko btana bhul jate ho..it's obvious but it completes the whole explaination structure!
Hi Sourabh sir has told that backtracking has a general formula - levels to the power of options. hope it helps
hanji. Ab lag rha hai ki sare questions ki redo kaise karoon. Aage se bnaunga
@@Pepcoding commnet section me daalke pin krdo , redo krne ki jroorat nhi :)
Sir how is this a backtracking solution ?
yeh test case kaise pass karenge?
Input: s = "(a)())()"
Output: ["(a())()","(a)()()"]
if character is coming just continue in for loop.
Awesome
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Java Solution accepted on leetcode
class Solution {
List result= new ArrayList();
HashSet visited;
public List removeInvalidParentheses(String s) {
if(s.length() ==0){
return result;
}
visited = new HashSet();
int mra = findInvalidRemoval(s);
getValidList(s,mra);
return result;
}
public void getValidList(String s,int minRemoval){
if(visited.contains(s)){
return ;
}
visited.add(s);
if(minRemoval == 0){
//check string formed is valid
int valid = findInvalidRemoval(s);
if(valid == 0){
result.add(s);
}
return ;
}
for(int i=0;i
Thanks a lot
Thanks :)
i did it on my own
cpp solution without tle::: i have done an optimisation to cut down rechecking of similar subproblem by using a map.
class Solution {
public:
vector ans;
unordered_map map;
int get_min(string s)
{
stack st;
for (int i = 0; i < s.size(); i++)
{
if (s[i] == '(')st.push('(');
else if (s[i] == ')')
{
if (st.size())
{
if (st.top() == '(')
{
st.pop();
}
else
{
st.push(')');
}
}
else
{
st.push(')');
}
}
}
return st.size();
}
void solve2(string s,int minimum_removal_allowed)
{
if(map[s]!=0)//for checking that string is already exist in map or not
return;
else
map[s]++;
if(minimum_removal_allowed==0)
{
int minimum_removal_now=get_min(s);
if(minimum_removal_now==0)
{
ans.push_back(s);
}
return;
}
for(int i=0;i
Post your queries on Community post of nados.io
Our mentors and alumni will guide you and help you out.
time complexity : N* 2^N ??
what was the concept of hashset in easy wording ???
Beta, I regret to inform you that, I won't be able to answer/solve the personal doubts of each and every student over here. For clearing your doubts, you can join our community on telegram - t.me/pepcoding.
❤️
sir time complexity kya hogi recursion fn ki
mast explanation, lol @ character and which
Keep learning beta
@@Pepcoding ji Prabhu ji
Sir please please parallel 2-3 dp ki super mast questions daaldo.
As soon as possible
PLease add Median of Two Sorted Arrays
Ji jaroor. Jaldi he
TLE on leetcode
Sir
Hanji
sir dont
Noice.
acknowledgement
Sir TLE kaise resolve karein iski?
Beta, I regret to inform you that, I won't be able to answer/solve the personal doubts of each and every student over here. For clearing your doubts, you can join our community on telegram - t.me/pepcoding.
Please use the below solution
class Solution {
List result = new ArrayList();
Set set1 = new HashSet();
public List removeInvalidParentheses(String s) {
int minRemovals = getMinRemoval(s);
System.out.println(minRemovals);
Set set = new HashSet();
removeInvalidParenthesesRecursion(s, minRemovals, set);
return result;
}
private void removeInvalidParenthesesRecursion(String s, int min, Set set){
if(min == 0){
int minRemovalAllowed = getMinRemoval(s);
if(minRemovalAllowed == 0){
if(!set.contains(s)){
set.add(s);
result.add(s);
}
}
return;
}
for(int i = 0; i < s.length(); i++){
String left = s.substring(0, i);
String right = s.substring(i+1);
if(!set1.contains(left+right)){
set1.add(left+right);
removeInvalidParenthesesRecursion(left+right , min - 1, set);
}
}
}
private int getMinRemoval(String str){
Stack stack = new Stack();
for(int i = 0; i < str.length(); i++ ){
char currentChar = str.charAt(i);
if(currentChar == '('){
stack.push(currentChar);
}
if(currentChar == ')'){
if(!stack.isEmpty() && stack.peek() == '('){
stack.pop();
} else {
stack.push(')');
}
}
}
return stack.size();
}
}
@@psettii Thanks for the solution!
Wchich
Great Video Sir !!!
So nice of you. May i request you to post us a reveiw?
g.page/Pepcoding/review?rc
@@Pepcoding Done, Please check