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

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

Рет қаралды 256,843

3 жыл бұрын

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

Пікірлер: 229

@takeUforward 3 жыл бұрын

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 3 жыл бұрын

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

@takeUforward 3 жыл бұрын

@@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 3 жыл бұрын

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

@parthdali9034 3 жыл бұрын

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 3 жыл бұрын

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 2 жыл бұрын

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

@dub161 7 ай бұрын

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

@laxminarayanchoudhary939 2 жыл бұрын

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

@ushakumari499 3 жыл бұрын

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

@atharvakulkarni2024 3 жыл бұрын

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 2 жыл бұрын

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

@bhaveshkumar6842 2 жыл бұрын

This is by far the best placement series!

@user-dg7pu8oo6v Жыл бұрын

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

@Tomharry910 Жыл бұрын

Very helpful. Thanks for the detailed explaination!

@shivangisrivastava1158 3 жыл бұрын

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

@anirudhatalmale5575 3 жыл бұрын

Super helpful. I think you missed the time complexity analysis

@VikasGupta-ok9lh Жыл бұрын

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

@DigvijaySingh-uu7yd 11 ай бұрын

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

@RandomShowerThoughts Жыл бұрын

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

@paragroy5359 3 жыл бұрын

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.

@akshanshsharma6025 Жыл бұрын

this guy is blessing for the students thank you bhai

@sakshamsengar9798 3 жыл бұрын

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

@stith_pragya Жыл бұрын

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

@RandomShowerThoughts Жыл бұрын

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

@ayushuniyal2586 Жыл бұрын

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

@Tomharry910 Жыл бұрын

Great video and explaination. Thank you!

@dipannitamahata1934 2 жыл бұрын

Please include explanation of the time complexity of the odes.

@fenil861 3 жыл бұрын

Awesome explanation .Thanks

@anandtripathi8464 3 жыл бұрын

Thanks bro i was troubling with backtracking step thanks again

@rydum2007 3 жыл бұрын

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

@abhishekpal4700 11 ай бұрын

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

@ShubhamMahawar_Dancer_Actor 3 жыл бұрын

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

@prabhaskoya Жыл бұрын

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

@lasanihussain8810 2 жыл бұрын

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

@nanda_8 2 жыл бұрын

it's n*(2^n)

@iamsalonitayal 2 жыл бұрын

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

@nanda_8 2 жыл бұрын

@@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 2 жыл бұрын

@@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 2 жыл бұрын

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

@aasthajha1051 3 жыл бұрын

awesome explanation, thankyou bhaiya..🙏🏻

@willturner3440 2 жыл бұрын

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

@alankritamishra4021 Жыл бұрын

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

@Anoyashu 3 жыл бұрын

amazing explanation !!!!

@9-teen77 3 жыл бұрын

wonderful explanation

@sahanagoudar1647 Жыл бұрын

kudos to your effort Striver

@jaskiratsinghosahan4638 3 жыл бұрын

Great explanation 👍

@bhumberg3243 3 жыл бұрын

explained so well:)

@ayushmamgain9040 13 күн бұрын

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

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

@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 2 ай бұрын

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

@tejaswininimbalkar7390 2 жыл бұрын

Can someone explain the Time Complexity?

@chitranshsaxena59 Жыл бұрын

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

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

@subhadeepghosh2813 3 жыл бұрын

great explaination 😍😍😍

@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 11 ай бұрын

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

@771aryan 10 ай бұрын

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

@iamnoob7593 7 ай бұрын

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 7 ай бұрын

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

@kunalkumarbarman9610 3 жыл бұрын

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 3 жыл бұрын

Nice explanation👍👍

@elabhattacharya892 3 жыл бұрын

Please make videos on leetcode competitions, hard problems on leetcode

@TanujaRS-m5m 4 күн бұрын

I have a question. We took the case where we include index i ( we include it in our string vector and then we call recursion on the next index). Shouldn't we consider the case of not taking that index at all? like just doing i+1 in the next recursion call without adding it to the vector? Am I missing anything here?

@gautamnegi-wh9xi 3 ай бұрын

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

@sleepypanda7172 2 жыл бұрын

Fantastic Flawless god level explanation!

@hooomansss984 8 ай бұрын

not that good eh

@albedo9617 2 ай бұрын

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?

@neyovyas3992 3 жыл бұрын

Nice explanation bro

@manavmalhotra8513 2 жыл бұрын

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

@abbasnaqvi5381 2 жыл бұрын

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

@BruteCode2002 Жыл бұрын

OMG wonderful Teaching way

@zealkapadiya4783 3 жыл бұрын

Thanks for the video 😊

@sbarbeloa 3 жыл бұрын

Thank you so much

@hardikpandey5349 3 жыл бұрын

Great work

@AkashKumar-lr6hc 2 жыл бұрын

Thanks for the video.

@abhimanyu6534 3 жыл бұрын

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

@Manojkumar-rq8hf 3 жыл бұрын

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

@anujrawat6304 2 жыл бұрын

great work

@symbol767 2 жыл бұрын

Thank you Striver

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

@deepaksarvepalli2344 2 жыл бұрын

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

@nishanttiwari9736 Жыл бұрын

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

@saikrishnalanka133 2 жыл бұрын

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 2 жыл бұрын

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

@saikrishnalanka133 2 жыл бұрын

@@ronitroushan2804 agree on that👍

@priyaagrawal8811 2 жыл бұрын

best explaination

@navendraagrawal 2 жыл бұрын

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

@nikhilsaharan 2 жыл бұрын

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

@UECAshutoshKumar Жыл бұрын

Thank you sir

@jeelanibasha3984 22 күн бұрын

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

@jaickey09 Жыл бұрын

God level explanation 😅

@tapasyadimree9651 4 ай бұрын

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 4 ай бұрын

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

@sathvikareddy9449 2 жыл бұрын

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

@webdesignersandip7469 6 ай бұрын

what's the time complexity of this?

@sowndaryav6680 3 жыл бұрын

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

@anjali3432 2 жыл бұрын

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

@kartikaymahajan9591 2 жыл бұрын

What is its time complexity?

@nithishd6420 3 жыл бұрын

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

@manojbabu7103 3 жыл бұрын

i think n*n! is time complexity

@lucky_raiser 2 жыл бұрын

@@manojbabu7103 i think n^n worst case

@ragnarT3 3 жыл бұрын

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 3 жыл бұрын

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

@pallavjain2749 2 жыл бұрын

@@anoopnuli8471 thankyou so much

@MaheshPatil-of1zy 15 күн бұрын

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

@dhruvgarg2271 25 күн бұрын

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

@ishikajaiswal4735 10 ай бұрын

thankyou soo much!!

@justlc7 2 ай бұрын

Gods gift.

@pragneshamadavadi2267 2 жыл бұрын

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 2 жыл бұрын

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 2 жыл бұрын

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

@the_good_bad_actors 2 жыл бұрын

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

@sushant8686 2 жыл бұрын

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

@arihantjammar8888 11 ай бұрын

understood!

@debapriyo007 6 ай бұрын

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

@AkshaySharma-bg3oj Жыл бұрын

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

@srinayan390 Жыл бұрын

god bless you dada♥

@yashgupta-fk3zc 3 жыл бұрын

bhaiya dp pe series kaab tak laaoge koi idea?

@hajeeramohamad7641 5 ай бұрын

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 4 ай бұрын

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 !

@satyampande684 2 жыл бұрын

understood!!

@shubhamchavan386 Жыл бұрын

what will be the time complexity

@harshitjaiswal9439 6 ай бұрын

understood.

@lakshmiprasanna7058 Жыл бұрын

Understood 💯💯💯

@TON-108 2 ай бұрын

Understood 💯💯

@besimplevlog3651 2 жыл бұрын

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

@physicslover3136 Жыл бұрын

what is the time complexity of the code

@eshanchourasia287 3 жыл бұрын

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

@ishaansalwan4017 2 жыл бұрын

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