L17. Palindrome Partitioning | Leetcode | Recursion | C++ | Java

Check our Website:
In case you are thinking to buy courses, please check below:
Link to get 20% additional Discount at Coding Ninjas: bit.ly/3wE5aHx
Code "takeuforward" for 15% off at GFG: practice.geeksforgeeks.org/co...
Code "takeuforward" for 20% off on sys-design: get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: indmoney.onelink.me/RmHC/idje...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
---------------------------------------------------------------------------------------------------------------------------------------------------- I have decided to make a free placement series comprising of video lectures(C++ and Java) on the entire SDE sheet.. ✅(bit.ly/takeUforward_SDE)
✅Entire Series: bit.ly/placementSeries
✅Problem Link: leetcode.com/problems/palindr...
C++/Java Code: takeuforward.org/data-structu...
Join this structured, industry relevant and guided program to Crack those upcoming Interviews. Check the Batch Trailer and Course Plan by clicking on the link. ELITE: Master Advanced Programming Topics and Become an Expert: unacademy.com/batch/elite-mas...
Access all the free live classes in the current week here: unacademy.cc/daily_learning
Use Code "TAKEUFORWARD" to get 10% of on subscription
✅This is where I teach: ----- Use coupon-code "TAKEUFORWARD" for getting 10% on my course at GFG: bit.ly/striver_cpCourse
✅Use coupon-code "TAKEUFORWARD" for getting 10% for all GFG courses: bit.ly/tuf_gfgCourse
If you appreciate the channel's work, you can join the family: bit.ly/joinFamily
Thumbnail Creator: / rikonakhuli
✅ Striver's Linkedin Profile: / rajarvp
✅ Instagram: / striver_79
Connect with us: t.me/Competitive_Programming_tuf (Use Link in Mobile only, if not works search "takeUforward" in telegram)..
#dsa #leetcode #placements

[@takeUforward]

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/​

[@harshitrathi3077]

Bro, Please add video daily or in 2 3 days ...... was waiting for you from last 10 days

[@takeUforward]

@@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 🤟🏼

[@harshitrathi3077]

@@takeUforward Okay Sure Sir , take care ... When will next Video Come ??

[@parthdali9034]

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.

[@prajwalbv4980]

what is the note app you use to write?

[@namangirdhar8736]

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 :).

[@lavanyam3224]

what happened to him?? hope he is fine now..

[@dub161]

Students give blessings to teacher now. Hey prabhu, what happened to my Bharat !!

[@laxminarayanchoudhary939]

Thank you so much for such a great collection of recursion problem and describing how to pick the approach.

[@Saurabh-fe2bg]

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

[@frickofunky2008]

I'm feeling very overwhelmed while learning java initially, any tips you would like to give me?

[@Saurabh-fe2bg]

@@frickofunky2008 go slow. Understand basic things first don't try to dive dip in the first go

[@frickofunky2008]

@@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 ?

[@Saurabh-fe2bg]

@@frickofunky2008 do web development..

[@leoved1073]

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??

[@ushakumari499]

Thanks bro u are doing great day by day...u are the best tutor on this platform in field of coding ...

[@atharvakulkarni2024]

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.

[@karthikk7136]

Great explanation i have ever seen on backtracking related problems🎇🎇

[@user-dg7pu8oo6v]

I did not need to look for the code after understanding the whole explanation. Amazingly explained

[@DigvijaySingh-uu7yd]

Great explanation of backtracking. Now I understand where I made a mistake in my code. Thank you

[@bhaveshkumar6842]

This is by far the best placement series!

[@Tomharry910]

Very helpful. Thanks for the detailed explaination!

[@paragroy5359]

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.

[@nagame859]

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..

[@tasneemayham974]

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!

[@nagame859]

Brilliant mate 🤩. Thanks a ton..

[@tasneemayham974]

@@nagame859 Sure!!

[@shreyxnsh.14]

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

[@ayushmamgain9040]

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).

[@sakshamsengar9798]

boht achha tha bhaia dil khush hogya thanku 4 ur everything..... jb job lgegi sbse pehle aap hi ko btaunga.......

[@VikasGupta-ok9lh]

The way u used pointers rather than passing string as a parameter was really nice

[@RandomShowerThoughts]

this is a great explanation. The visuals are great ways to see this

[@shivangisrivastava1158]

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✨♥️

[@akshanshsharma6025]

this guy is blessing for the students thank you bhai

[@ayushuniyal2586]

learning through all your videos and liking your videos too.please make solutions of heaps on SDE SHEET:)

[@pragneshamadavadi2267]

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.

[@gauravshukla6675]

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

[@pragneshamadavadi2267]

@@gauravshukla6675 we are using it to track the character of string that left to match yet.

[@the_good_bad_actors]

@@gauravshukla6675 working of substr is like --> substr(from which index, how many character you want to take)....hope that this will be helpful

[@sushant8686]

brother how 2 ^ n for every character we have n options na ?

[@ravisingh-el8np]

@@sushant8686 we have a choice to partition or not at given at index that's why

[@surendrapandey4660]

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.

[@ritikshrivastava9442]

actually the tc is O(n*2^n-1) for n length string 2^n-1 partition possible 2^n is subsequence

[@771aryan]

what about the timecomplexity of copying the sequence into a new vector for storing in the list?

[@iamnoob7593]

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.

[@cosmostravelar]

N/2 is correct but it's not n^n it's actually 2 ^n

[@RandomShowerThoughts]

thanks for explaining this so damn well, I have having such a hard time comprehending this from Aditya's video

[@anirudhatalmale5575]

Super helpful. I think you missed the time complexity analysis

[@stith_pragya]

UNDERSTOOD.........Thanks a ton Striver Brother......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@anandtripathi8464]

Thanks bro i was troubling with backtracking step thanks again

[@Tomharry910]

Great video and explaination. Thank you!

[@lasanihussain8810]

Please also include Time complexity analysis , i find it difficult to do for recursive problems.

[@nanda_8]

it's n*(2^n)

[@iamsalonitayal]

@@nanda_8 shouldn't it be O(n!) as we are not making only two choices per element.

[@nanda_8]

@@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

[@iamsalonitayal]

@@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.

[@vishwanathbhat3019]

@@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))

[@abhishekpal4700]

thanks bro, for your dsa videos i can have some hope in life

[@rydum2007]

@Striver bhai yaar gajab samjhaye ho sb aasan ho gya h

[@aasthajha1051]

awesome explanation, thankyou bhaiya..🙏🏻

[@fenil861]

Awesome explanation .Thanks

[@prabhaskoya]

Thank you bhai, i was able to solve this before watching video

[@alankritamishra4021]

Really good Stuff, please have a session how you come up with solutions or logic building

[@dipannitamahata1934]

Please include explanation of the time complexity of the odes.

[@akshittomar2401]

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 .

[@Anoyashu]

amazing explanation !!!!

[@ShubhamMahawar_Dancer_Actor]

what would be the T.C O(2^n) and S.C O(N) or something else?

[@willturner3440]

Sir, you haven't discussed about time complexity.. Please if anyone knows

[@jaskiratsinghosahan4638]

Great explanation 👍

[@bhumberg3243]

explained so well:)

[@9-teen77]

wonderful explanation

[@tejaswininimbalkar7390]

Can someone explain the Time Complexity?

[@chitranshsaxena59]

Can someone explain how to calculate time complexity in this case?

[@albedo9617]

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?

[@subhadeepghosh2813]

great explaination 😍😍😍

[@sahanagoudar1647]

kudos to your effort Striver

[@abbasnaqvi5381]

gives the same string as the output always. i.e if the input is "aabb" then the code will output "aabb" 4 times . how will we understand where we have partitioned the string

[@kunalkumarbarman9610]

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.

[@vinaychhillar2230]

Nice explanation👍👍

[@manavmalhotra8513]

func(i + 1, s, path, res); why we incremented i ?

[@gautamnegi-wh9xi]

Instead of looping can we also use recursion, like passing index 1 by 1?

[@neyovyas3992]

Nice explanation bro

[@zealkapadiya4783]

Thanks for the video 😊

[@nikhilsaharan]

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

[@MaheshPatil-of1zy]

Some Recursion Call are Missing at the end of {a,a,b,b} formation

[@hardikpandey5349]

Great work

[@BruteCode2002]

OMG wonderful Teaching way

[@elabhattacharya892]

Please make videos on leetcode competitions, hard problems on leetcode

[@saikrishnalanka133]

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.

[@ronitroushan2804]

yep you are right you can use dp, but here in this question constraints are too small so he has use recursion

[@saikrishnalanka133]

@@ronitroushan2804 agree on that👍

[@sleepypanda7172]

Fantastic Flawless god level explanation!

[@hooomansss984]

not that good eh

[@AkashKumar-lr6hc]

Thanks for the video.

[@sowndaryav6680]

Thank you so much sir...u will completely recover soon sir😊

[@nishanttiwari9736]

23:54 WHAT IF WE DONT PASS THE PATH BY REFERENCE THEN DO WE NEED TO POP IT IN THE END?

[@Anurag-tg2hr]

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.

[@ShubhamPandey-st4nn]

After partitioning, you get several substrings. That substrings should be palindrome.

[@sbarbeloa]

Thank you so much

[@anujrawat6304]

great work

[@tapasyadimree9651]

when we are making partitions at 0 index. and check if we can make a partition for substring 0 to 3 (that is aabb), wouldn't that be a valid partition ? because the palindrome function is going to give true for this. so "aabb | " should also be a valid partition and should be visible in the output, but why is it not ? I tried to do a dry run too but still can't figure out how the code is preventing "aabb" from being included in the answer ? can someone explain ?

[@farazjawaid2982]

see basically "aabb" ka palindrome would be "bbaa" so thats why it isnt included in the output !

[@jeelanibasha3984]

This program will create sequential substrings of palindrome only right?? It means if we took 3213 it won't produce 33???

[@abhimanyu6534]

What about Time comp and space complexity Plz reply I don't understand that

[@Manojkumar-rq8hf]

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

[@sathvikareddy9449]

y cant we partition after "aabb"(aabb|).its a substring right?

[@deepaksarvepalli2344]

Seems easy while you explaining but can't able to come up with solution before watching video

[@ragnarT3]

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

[@anoopnuli8471]

in c++ substr() function second argument will take len of the substring.

[@pallavjain2749]

@@anoopnuli8471 thankyou so much

[@kartikaymahajan9591]

What is its time complexity?

[@navendraagrawal]

can anyone explain me when to pass i+1 and when to pass index+1 in the recursive call ??? please

[@anshumaan1024]

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

[@anjali3432]

why we are doing ++i instead of i++?

[@debapriyo007]

Can anyone tell me what is th TC ? I think it may be exponentially but how can i make recurring relation and cal that?

[@priyaagrawal8811]

best explaination

[@hajeeramohamad7641]

What's the difference between doing i+1 and ind+1? It always confuses me. Aren't they same? Both i and and ind are 0. What difference does it make if we do i+1 or ind+1? Either way, if we do i+1, won't that increment index too?

[@farazjawaid2982]

okay idk how well can i tell without a diagram... but i+1 is when , in the height of a tree we are going on the next level ....like if i am on the root node i am at level 0 then i do " i+1 " so now i reach the child nodes of the root ....on the other hand ind+1 is just to go to the next index of the current case or situation being dealt with !

[@besimplevlog3651]

if 0 position is pallindromic then why we storing 0 to i+1 it should be 0 t0 i right i am not getting this

[@dhruvgarg2271]

please someone explain time and space complexity in detail for better understanding @TUF

[@symbol767]

Thank you Striver

[@jaickey09]

God level explanation 😅

[@nithishd6420]

is the time complexity is O(2^n) and space complexity O(n)?

[@manojbabu7103]

i think n*n! is time complexity

[@lucky_raiser]

@@manojbabu7103 i think n^n worst case

[@yogeshyts]

9:28 this is not backtracking bro this is function control goes to where it was called in backtracking we change the changes to its original state that we have made to achieve the answer in future calls

[@vijayakumareyunni6010]

I can't understand the "strategy" at all. Asking to "partition here", or "partition there" doesn't help.

[@eshanchourasia287]

Base case ,index should be s.length-1?

[@ishaansalwan4017]

No because we will consider the element present at length-1 , for base case try to think of the smallest invalid input which will be length as if we try to access it we will get garbage value or error

[@AbhinavSingh-up7bl]

I HAVE A QUESTION!!!! I was able to do all this by my own but I was doing list.push_back(s.substr(idx,i+1)); // and giving some wrong substring :: still i'm confused why you were doing list.push_back(s.substr(idx,idx-i+1)); :: because you had done the same (idx,i+1) in java code but (index,index-i +1) on c++ whyyyyy??

[@mdahsanulhaqueshantanur2760]

in C++ second argument of substr() function is length of substring, while in Java is the end point.

[@satyampande684]

understood!!

[@arihantjammar8888]

understood!

[@ishikajaiswal4735]

thankyou soo much!!

[@webdesignersandip7469]

what's the time complexity of this?

[@UECAshutoshKumar]

Thank you sir

[@peregrine17]

you have written (i + 1) in 16th line of Java code, but you haven't mentioned why you wrote (i - index + 1) 18th line of c++ code.

[@komalchaudhary2542]

because the substr function takes 2 parameters, first is the starting index and second is the length of substr which is i-index+1

[@AkshaySharma-bg3oj]

striver : "you no how to loop?" emotional damage

[@physicslover3136]

what is the time complexity of the code

[@aditisrivastava7548]

In c++ code what is the logic of using substr(index,i-index+1)

[@sidhantjha4566]

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.

[@nagame859]

@@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?

[@studyonly9622]

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

[@farazjawaid2982]

could someone explain how he got the ( i-ind+1) fo the substring !?

[@tapasyadimree9651]

it's because substr function takes two inputs (index, length) so here we are passing the length upto which we want the substring, this length is calculated by ( i - ind + 1 ) can you see my doubt above and see if you can help ?

[@sleepypanda7172]

I wish I could give multiple likes here