Are you going to take the upcoming GFG Cp course from March 20 Live or it will be recorded session of previous batches? Please answer as you went through the operation recently. Hence confused.
All i can say is you have blessings of thousands of students , you are doing an excellent work , you inspire us to work hard , Thanks a lot , wish u have a speedy recovery :).
bro, bcoz of u I got the confidence, that DSA is no Rocket Science and could be solve with ease if we have proper guidance and community. Thanks man!! God Bless,, btw completed Graphs, Trees and DP series it was amazing!! thanks a ton
@@Saurabh-fe2bg bro I'm already a gap year student meaning. I haven't been in a job ever since I did my btech. Do you think it's still viable to do DSA or should I do direct development in these 3-4 months and apply to jobs directly ?
Time Complexity is O( N * 2^N) where N to store the path in ans and 2^N for generating subsequence And the Space Complexity is O( N * N ) , where N to store subsequence in path vector and N for recurssion tree.
can you make me understand how s.substr(index,i-index+1) is working because i am not able to understand why we are not using s.substr(index,i+1)//suppose when i = 0 and index is also 0 then s.substr would be (0,0 - 0 +1) which will give nothing ...please it would be very helpful if you can clear my doubt
Instead of calling the isPalindrome(String s) function again and again to check weather the partitioned string is palindrome or not, we can use some precomputations. A boolean array of size N * N (lets call it dp) can be used to pre-compute weather a substring from index i to j (s.substring(i, j+1)) is a palindrome or not. It will be stored in dp[i][j] as either true or false. This will boil down the additional O(N) required by isPalindrome() function to O(1).
The time complexity of the algorithm for generating all possible palindromic partitioning is typically expressed as O(n * 2^n), where n is the length of the input string. This complexity arises because there can be 2^n possible partitions, and for each partition, we need to check if each substring is a palindrome, which takes O(n) time in the worst case.
Love you bhaiya , video abhi dekhi nahi h puri , Just want to tell you that you are our warrior, our savior ♥️💎 Hope you have a speedy recovery brother✨♥️
@@iamsalonitayal No We can generate at Max 2^n subsequences I ignored the time to check if string is palindrome and also ignored time to insert the string to final answer vector
@@nanda_8 I am talking of time complexity. If we consider case where s = "aaaa" then loop will be till n in first level, (n-1)+(n-2).. in second, (n-2)+(n-3)... in third and so on till n=1 or n=0. So it would benx(n-1)x(n-2)... its n!. isn't it? and for space complexity O(k x n) where n = avg length of a partition array string and k is average no of partition arrays.
@@iamsalonitayal Time complexity: O(n*(2^n)) For a string with length n, there will be (n - 1) intervals between chars. For every interval, we can cut it or not cut it, so there will be 2^(n - 1) ways to partition the string. For every partition way, we need to check if it is palindrome, which is O(n). So the time complexity is O(n*(2^n))
Wonderfull, Quality Content ...Waiting for the next videos..Its a humble request please make videos faster so that we can complete it till our placements(june)..Please thanks a ton for such wonderfull content.
Quite understandable one! But the code for C++ for adding substring is a bit confusing. Java has (index,i+1) which is quite understandable. But, this one is a bit complex to understand with (index,i-index+1). Why is that? I have also done the dry run, with (index, i+1), but the solution ain't correct. What's the logic behind this? It's the same logic and function in Java and C++ isn't it? Anyone please clarify..
Yes, that's my question too. If you dry run the code with only i, you get an empty string at the beginning because the partition from 0 to 0 is nothing. If you try with i+1, you get some characters get repeated. So, you are right since both C++ and java have the same logic, why are the codes different? It must have something to do with the substring method in C++ itself. So, I looked into it. Turns out that the C++ substr isn't the same as Java substring method. While in Java the parameters of substring indicate the beginning and end, in C++ the method's first parameter takes the beginning and the second takes THE NUMBER OF CHARACTERS IN THE SUBSTRING. Hence to get the number of chars you have to subtract the ind from i and add 1. Because suppose we are at ind 0 at i =0, we have one character. So that's 0-0+1 =1. Now if we are at ind =2 and i =3, there are two characters so 3-2+1. I hope I made it clear to you. Tell me if you got it!
Nice explanation sir.......thanks a lot for the video....I got highly motivated when I see the amount of hardwork that you are doing in your life.You are my rolemodel.
No this is not. Its just the person having best solution (in terms of time) have used the function name as backtracking. otherwise it is not. But if we deep dive , we will still able to apply dynamic programming.
I think time complexity for this question is Theta(n^2)*(n!) bcz 1st time 1st letter is cut from string , 2nd time 2 letters , 3rd time 3 letters we do it till complete string 'n' is selected so n! and average sub-strings each time will be 'n' sub-strings and for each n sub-strings we are checking for palindrome so n^2 operation each time . THERFORE: Theta(n^2)*(n!) PLLZ TELL IF THIS IS CORRECT .
I think the time complexity would be O(n^n). Because for every level of the recursion tree we are calculating for almost n children! And same for the space complexity. What say?
U dont need index , just use the string class Solution { public: vector partition(string s) { vector list; vector ans; partition(ans,list,s); return ans;
maybe we also need memorisation here, as if there is a plaindrome substring from indices i to j then there will be repetitions in calculation of result of string after index j
I think they are repeating subproblems where we are checking if a substring is palindrome again and again we can make use of dynamic programming to make it more optimal.
class Solution { public: bool ispallindrome(string s, int i) { int n = s.length(); if (i >= n / 2) return true; if (s[i] != s[n - 1 - i]) { return false; } return ispallindrome(s, i + 1); } void sol(vector& ans, vector& ds, string s, string d, int i) { if (i == s.length()) { for (auto i : ds) { if (ispallindrome(i, 0) == false) { return; } } ans.push_back(ds); return; } d += s[i]; ds.push_back(d); sol(ans, ds, s, "", i + 1); if (i < s.length() - 1) { ds.pop_back(); sol(ans, ds, s, d, i + 1); } } vector partition(string s) { vector ans; vector ds; string d = ""; int i = 0; sol(ans, ds, s, d, i); return ans; } }; Can someone plz explain what is the issue with my approach?
Might be a basic question but when we add path to the list why don't we just do res.add(path) directly? Why are we creating a new ArrayList(path) and then pushing it?
Time complexity : exponential in nature (as we are doing recursive call for all palindromic substring) Space complexity : cannot be predicted (because based on list of palindromic strings, it may vary) . If anyone thinks it's wrong, please correct me
Thanks for the sheet i am enjoying .. can you please do one more favour can you please add all the problem link which doesn't have video. Sometime it is difficult to find that particular problem.
In C++ code, line number 18 why do we use substr(indx,i-indx+1)... Also why does it give wrong answer for substr(indx,i+1) ? Anyone... Thank you in advance
In the question it is given that every substring of the partition must be a palindrome, but when we give the input as "aaba" we are getting an array ["a,"aba"] in the solution, where every substring in the string "aba" is not a palindrome, can you please explain this.
@@sidhantjha4566 yes, but the same code in Java has (index,i+1) which is quite understandable. But, this one is a bit complex to understand. I have also done the dry run, with (index, i+1), but the solution ain't correct. Why is that? It's the same logic and function in Java and C++ isn't it?
C++ Code Link: github.com/striver79/SDESheet/blob/main/PalindromePartitioningCpp
Java Code Link: github.com/striver79/SDESheet/blob/main/PalindromePartitioningJava
Instagram: instagram.com/striver_79/
Bro, Please add video daily or in 2 3 days ...... was waiting for you from last 10 days
@@harshitrathi3077 am not sure if you know or not, I just had a major operation. You can join telegram group to know about regular updates 🤟🏼
@@takeUforward Okay Sure Sir , take care
... When will next Video Come ??
Are you going to take the upcoming GFG Cp course from March 20 Live or it will be recorded session of previous batches? Please answer as you went through the operation recently. Hence confused.
what is the note app you use to write?
All i can say is you have blessings of thousands of students , you are doing an excellent work , you inspire us to work hard , Thanks a lot , wish u have a speedy recovery :).
what happened to him?? hope he is fine now..
Students give blessings to teacher now.
Hey prabhu, what happened to my Bharat !!
Thank you so much for such a great collection of recursion problem and describing how to pick the approach.
bro, bcoz of u I got the confidence, that DSA is no Rocket Science and could be solve with ease if we have proper guidance and community.
Thanks man!! God Bless,, btw completed Graphs, Trees and DP series it was amazing!! thanks a ton
I'm feeling very overwhelmed while learning java initially, any tips you would like to give me?
@@frickofunky2008 go slow. Understand basic things first don't try to dive dip in the first go
@@Saurabh-fe2bg bro I'm already a gap year student meaning. I haven't been in a job ever since I did my btech. Do you think it's still viable to do DSA or should I do direct development in these 3-4 months and apply to jobs directly ?
@@frickofunky2008 do web development..
23:52 I have question here as we are not increasing the value of index how index is going to reach end and base case going to trigger??
Super helpful. I think you missed the time complexity analysis
Time Complexity is O( N * 2^N) where N to store the path in ans and 2^N for generating subsequence And the Space Complexity is O( N * N ) , where N to store subsequence in path vector and N for recurssion tree.
can you make me understand how s.substr(index,i-index+1) is working because i am not able to understand why we are not using s.substr(index,i+1)//suppose when i = 0 and index is also 0
then s.substr would be (0,0 - 0 +1) which will give nothing ...please it would be very helpful if you can clear my doubt
@@gauravshukla6675 we are using it to track the character of string that left to match yet.
@@gauravshukla6675 working of substr is like --> substr(from which index, how many character you want to take)....hope that this will be helpful
brother how 2 ^ n for every character we have n options na ?
@@sushant8686 we have a choice to partition or not at given at index that's why
Instead of calling the isPalindrome(String s) function again and again to check weather the partitioned string is palindrome or not, we can use some precomputations.
A boolean array of size N * N (lets call it dp) can be used to pre-compute weather a substring from index i to j (s.substring(i, j+1)) is a palindrome or not. It will be stored in dp[i][j] as either true or false.
This will boil down the additional O(N) required by isPalindrome() function to O(1).
Thanks bro u are doing great day by day...u are the best tutor on this platform in field of coding ...
Great explanation i have ever seen on backtracking related problems🎇🎇
The time complexity of the algorithm for generating all possible palindromic partitioning is typically expressed as O(n * 2^n), where n is the length of the input string. This complexity arises because there can be 2^n possible partitions, and for each partition, we need to check if each substring is a palindrome, which takes O(n) time in the worst case.
actually the tc is O(n*2^n-1)
for n length string 2^n-1 partition possible
2^n is subsequence
what about the timecomplexity of copying the sequence into a new vector for storing in the list?
TC is N^N , N recursive calls at each stage , Overall : O(N^N * (N/2 + N)) , N for substring generation and n/2 for palindrome check.
N/2 is correct but it's not n^n it's actually 2 ^n
Love you bhaiya , video abhi dekhi nahi h puri ,
Just want to tell you that you are our warrior, our savior ♥️💎 Hope you have a speedy recovery brother✨♥️
UNDERSTOOD.........Thanks a ton Striver Brother......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Please also include Time complexity analysis , i find it difficult to do for recursive problems.
it's n*(2^n)
@@nanda_8 shouldn't it be O(n!) as we are not making only two choices per element.
@@iamsalonitayal No
We can generate at Max 2^n subsequences
I ignored the time to check if string is palindrome and also ignored time to insert the string to final answer vector
@@nanda_8 I am talking of time complexity. If we consider case where s = "aaaa" then loop will be till n in first level, (n-1)+(n-2).. in second, (n-2)+(n-3)... in third and so on till n=1 or n=0. So it would benx(n-1)x(n-2)... its n!. isn't it? and for space complexity O(k x n) where n = avg length of a partition array string and k is average no of partition arrays.
@@iamsalonitayal
Time complexity: O(n*(2^n))
For a string with length n, there will be (n - 1) intervals between chars.
For every interval, we can cut it or not cut it, so there will be 2^(n - 1) ways to partition the string.
For every partition way, we need to check if it is palindrome, which is O(n).
So the time complexity is O(n*(2^n))
This is by far the best placement series!
I did not need to look for the code after understanding the whole explanation. Amazingly explained
The way u used pointers rather than passing string as a parameter was really nice
Wonderfull, Quality Content ...Waiting for the next videos..Its a humble request please make videos faster so that we can complete it till our placements(june)..Please thanks a ton for such wonderfull content.
@Striver bhai yaar gajab samjhaye ho sb aasan ho gya h
Great explanation of backtracking. Now I understand where I made a mistake in my code. Thank you
learning through all your videos and liking your videos too.please make solutions of heaps on SDE SHEET:)
I am so grateful of the work you do!
boht achha tha bhaia dil khush hogya thanku 4 ur everything..... jb job lgegi sbse pehle aap hi ko btaunga.......
Quite understandable one!
But the code for C++ for adding substring is a bit confusing. Java has (index,i+1) which is quite understandable. But, this one is a bit complex to understand with (index,i-index+1). Why is that? I have also done the dry run, with (index, i+1), but the solution ain't correct. What's the logic behind this? It's the same logic and function in Java and C++ isn't it? Anyone please clarify..
Yes, that's my question too. If you dry run the code with only i, you get an empty string at the beginning because the partition from 0 to 0 is nothing. If you try with i+1, you get some characters get repeated. So, you are right since both C++ and java have the same logic, why are the codes different? It must have something to do with the substring method in C++ itself.
So, I looked into it. Turns out that the C++ substr isn't the same as Java substring method. While in Java the parameters of substring indicate the beginning and end, in C++ the method's first parameter takes the beginning and the second takes THE NUMBER OF CHARACTERS IN THE SUBSTRING. Hence to get the number of chars you have to subtract the ind from i and add 1. Because suppose we are at ind 0 at i =0, we have one character. So that's 0-0+1 =1. Now if we are at ind =2 and i =3, there are two characters so 3-2+1.
I hope I made it clear to you. Tell me if you got it!
Brilliant mate 🤩. Thanks a ton..
@@nagame859 Sure!!
class Solution {
public:
bool isPalindrome(string &str, int i = 0){
if (str[i] != str[str.size() - i - 1])
return false;
else if (i == str.size() / 2)
return true;
return isPalindrome(str, i+1);
}
void recursion(string &s, vector &ans, vector res){
if(s.empty()){
ans.push_back(res);
}
for(int i=0;i
Thanks, Your way of explaning is really great
Nice explanation sir.......thanks a lot for the video....I got highly motivated when I see the amount of hardwork that you are doing in your life.You are my rolemodel.
kudos to your effort Striver
Thank you bhai, i was able to solve this before watching video
Very helpful. Thanks for the detailed explaination!
I know this is not backtracking but they are so very similar approach. Kudos.
No this is not. Its just the person having best solution (in terms of time) have used the function name as backtracking. otherwise it is not. But if we deep dive , we will still able to apply dynamic programming.
this guy is blessing for the students thank you bhai
thanks bro, for your dsa videos i can have some hope in life
class Solution {
public:
bool checkPalindrone(string a){
string _a = a;
reverse(a.begin(),a.end());
if(_a==a)return true;
return false;
}
void helper(string s,vector&vec,vector&ref,int index){
if(index==s.size()){
vec.push_back(ref);
return;
}
string _ = "";
for(int i = index;i
OMG wonderful Teaching way
Fantastic
Flawless
god level explanation!
not that good eh
I think time complexity for this question is Theta(n^2)*(n!) bcz 1st time 1st letter is cut from string , 2nd time 2 letters , 3rd time 3 letters we do it till complete string 'n' is selected so n! and average sub-strings each time will be 'n' sub-strings and for each n sub-strings we are checking for palindrome so n^2 operation each time . THERFORE: Theta(n^2)*(n!)
PLLZ TELL IF THIS IS CORRECT .
thanks for explaining this so damn well, I have having such a hard time comprehending this from Aditya's video
Really good Stuff, please have a session how you come up with solutions or logic building
Please include explanation of the time complexity of the odes.
I think the time complexity would be O(n^n). Because for every level of the recursion tree we are calculating for almost n children! And same for the space complexity. What say?
this is a great explanation. The visuals are great ways to see this
what would be the T.C O(2^n) and S.C O(N) or something else?
Sir, you haven't discussed about time complexity.. Please if anyone knows
U dont need index , just use the string
class Solution {
public:
vector partition(string s) {
vector list;
vector ans;
partition(ans,list,s);
return ans;
}
private:
bool isPalindrome(string& str)
{
string r_str=str;
reverse(r_str.begin(),r_str.end());
return str==r_str;
}
void partition( vector& ans,vector& list,string s)
{
if(s.size()==0)
{
ans.push_back(list);
}
for(int i=1;i
Awesome explanation .Thanks
Can someone explain the Time Complexity?
Great video and explaination. Thank you!
maybe we also need memorisation here, as if there is a plaindrome substring from indices i to j then there will be repetitions in calculation of result of string after index j
Thank you sir
Seems easy while you explaining but can't able to come up with solution before watching video
Thanks a lot !!
Understooooooodddd , easyyyyyy
I think they are repeating subproblems where we are checking if a substring is palindrome again and again we can make use of dynamic programming to make it more optimal.
yep you are right you can use dp, but here in this question constraints are too small so he has use recursion
@@ronitroushan2804 agree on that👍
wonderful explanation
Thank you Striver
Please make videos on leetcode competitions, hard problems on leetcode
Thanks for the video.
class Solution {
public:
bool ispallindrome(string s, int i) {
int n = s.length();
if (i >= n / 2)
return true;
if (s[i] != s[n - 1 - i]) {
return false;
}
return ispallindrome(s, i + 1);
}
void sol(vector& ans, vector& ds, string s,
string d, int i) {
if (i == s.length()) {
for (auto i : ds) {
if (ispallindrome(i, 0) == false) {
return;
}
}
ans.push_back(ds);
return;
}
d += s[i];
ds.push_back(d);
sol(ans, ds, s, "", i + 1);
if (i < s.length() - 1) {
ds.pop_back();
sol(ans, ds, s, d, i + 1);
}
}
vector partition(string s) {
vector ans;
vector ds;
string d = "";
int i = 0;
sol(ans, ds, s, d, i);
return ans;
}
};
Can someone plz explain what is the issue with my approach?
Thanks bro i was troubling with backtracking step thanks again
Some Recursion Call are Missing at the end of {a,a,b,b} formation
I wish I could give multiple likes here
awesome explanation, thankyou bhaiya..🙏🏻
Gods gift.
god bless you dada♥
explained so well:)
God level explanation 😅
Nice explanation bro
Might be a basic question but when we add path to the list why don't we just do res.add(path) directly? Why are we creating a new ArrayList(path) and then pushing it?
thankyou soo much!!
Understood 💯💯💯
Great explanation 👍
func(i + 1, s, path, res);
why we incremented i ?
great explaination 😍😍😍
What about Time comp and space complexity
Plz reply I don't understand that
Time complexity : exponential in nature
(as we are doing recursive call for all palindromic substring)
Space complexity : cannot be predicted (because based on list of palindromic strings, it may vary) .
If anyone thinks it's wrong, please correct me
thank u so much striver!
seen this comment and hve a feeling something familiar
best explaination
Can someone explain how to calculate time complexity in this case?
Thanks for the video 😊
Understood ❤
simpler version of code(without use of substr):
bool isPalindrome(string s)
{
int start = 0, end = s.size()-1;
while (start
Thank you so much
Great work
Maza aa gya
understood!
Understood!!
UNDERSTOOD;
Understood!
striver : "you no how to loop?" emotional damage
Instead of looping can we also use recursion, like passing index 1 by 1?
please someone explain time and space complexity in detail for better understanding @TUF
T.C: O(N * 2^N) S.C: O(N)
understood.
I can't understand the "strategy" at all. Asking to "partition here", or "partition there" doesn't help.
Thank you so much sir...u will completely recover soon sir😊
This program will create sequential substrings of palindrome only right?? It means if we took 3213 it won't produce 33???
Thanks for the sheet i am enjoying .. can you please do one more favour can you please add all the problem link which doesn't have video. Sometime it is difficult to find that particular problem.
In C++ code, line number 18 why do we use substr(indx,i-indx+1)... Also why does it give wrong answer for substr(indx,i+1) ? Anyone... Thank you in advance
in c++ substr() function second argument will take len of the substring.
@@anoopnuli8471 thankyou so much
In the question it is given that every substring of the partition must be a palindrome, but when we give the input as "aaba" we are getting an array ["a,"aba"] in the solution, where every substring in the string "aba" is not a palindrome, can you please explain this.
After partitioning, you get several substrings. That substrings should be palindrome.
superb
Understood
can anyone explain me when to pass i+1 and when to pass index+1 in the recursive call ??? please
agar (index-i) palindrome hoga tabhi f(i+1,s,path,res) ko call krna hai.. samje ? nahi samjhe toh dry run krke dekh lo
understood!!
In c++ code what is the logic of using substr(index,i-index+1)
substr is used for cutting down the string the first parameter refers to the starting point and the second parameter refers to the end position.
@@sidhantjha4566 yes, but the same code in Java has (index,i+1) which is quite understandable. But, this one is a bit complex to understand. I have also done the dry run, with (index, i+1), but the solution ain't correct. Why is that? It's the same logic and function in Java and C++ isn't it?