DP 53. Palindrome Partitioning - II | Front Partition 🔥

[@aayush5474]

How is Time complexity N^2? What about the extra loop for checking palindrome?

[@takeUforward]

Oops missed it, my bad, you are correct.

[@yuvi3398]

@@takeUforward We can create another dp table in which dp[I][j] will tell whether substring s(I,j) is palindrome or not hence check function's time complexity reduces to O(1) and overall time complexity to O(n^2)

[@takeUforward]

@@yuvi3398 yes pre computations will help

[@himanshuparihar7423]

@@takeUforward Sir I submitted the same question on leetcode but it's giving TLE even in the tabulation part it's giving TLE. But when I used recursive way to check Palindrome... it got accepted....can you explain why recursive way accepted but the iterative method is giving TLE..

[@harshdasila6680]

@@himanshuparihar7423 did you find any solution for that bro

[@rohitraj5832]

at 20:08.TC shoyuld be N^3 bcz everytime we are checking for palindrome also. it will also take O(n) time in worst case

[@7akon]

This can be boiled down to n^2. Check the parameters in the recursive function. Where are we using n? You can simply compute it to be str.length(). So the recursive parameters are simply: fn(string, start). And another linear factor introduced by the palindrome check. So n^2. The iterative code in this video is n^3 but the recursive code will be bounded by O(n^2).

[@adrijsharma8404]

I think the time complexity is O(N^3). We have the recursion stack taking O(N). Inside each resusion step we have the j loop [O(n)] and inside each j loop we have the isPalindrome function which is O(n) again. n * n * n = n^3.

[@balakrishnanr648]

How in leeetcode 1e3 contraint runs on O(N^3)

[@iamnoob7593]

yes u r right ,

[@abhishekverma7604]

its a classical LPS variation..longest the palindromic substring partioned,minimum are the cuts... it was asked by meta recently in our on campus drive...

[@maceback6622]

We can find the longest palindromic substring but it is not sufficient to get the minimum cuts, because we have to identify other smaller palindromic substrings as well. Correct me if I'm wrong.

[@stith_pragya]

UNDERSTOOD.......Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@cacklouncle]

Base case i == n ki jagah aisa lelo ki starting index se end tak puri string palindrome hai toh return 0. Aise last mein -1 bhi nahin karna padega aur time bhi kaafi bachega jaise test case mein bahut badi string hai jo already palindrome hai, toh recursive calls jayengi hi nahin straightaway 0 ans

[@dawarvaibhav]

Was able to solve on my own after your previous videos. Well taught as always! :)

[@harshkankariya4423]

its tc wil be O(n^3) because we r chwcking for valid palindrome also

[@deepanshurohilla2114]

14:42 That was epic 😂😂😂😂

[@lakshitjuneja7530]

when you did it was a medium question now this is a hard question may b test cases got more strict that's why this solution is giving TLE in large input

[@yugal8627]

I had watched you Palindrome Partitioning-1 video and I had able to solve this by my own..😃

[@sayansahu4594]

Pass the string by reference to the Palindrome function to avoid getting a TLE

[@JE_Dinesh]

But why? What difference is it making? auxiliary space decreases right?

[@sauravlogsvio1891]

@@JE_Dinesh class Solution { public: bool isPalindrome(string& s, int start, int end) { while(start = j) return 0; if(cache[i] != -1) return cache[i]; if(isPalindrome(s, i, j)) return 0; int minCuts = INT_MAX; // Try all possible cuts between i and j for(int k=i; k

[@JE_Dinesh]

@@sauravlogsvio1891 i don't want solution code, i need explanation to it.

[@sauravlogsvio1891]

@@JE_Dinesh Pass by reference will be faster as you don't have to create and copy the whole string millions of times in the function call.. which takes memory as well as the time it takes to create as well. So, it's recommended to just pass a reference to it.

[@JE_Dinesh]

@@sauravlogsvio1891 thanks a lot bhai🤩

[@prasunroy2802]

Leetcode isn't accepting all test cases for java. We will have to store the possible palindromes in form of a 2d matrix and access this matrix when checking for the isPalin condition in the recurrence.

[@solitaryassasin]

This can be solved by the traditional MCM pattern too. Partition at a place and check for min partitions on left and right.

[@anishmangal9072]

But Time complexity there will be O(N*N*(N+N)) that is equal to O(n3) -->

[@solitaryassasin]

@@anishmangal9072 Here also it's N³

[@swetanksrivastava3159]

Shouldn't the time complexity be O(N*N*N*N) i.e one for the i loop, one for the j loop, one for the k loop ,and one for the palindrome checking. Although, it can be optimised to O(N*N*N) by palindrome precomputation....please correct me if I am wrong.....Also I am seriously confused as to when we should apply front partitioning and traditional mcm approach respectively...

[@sarthakgupta290]

It will be O(N^3) and will time out on LeetCode #132

[@10minutes_cs]

can u explain a bit more ? @solitaryassasin , we will try to put partition at each point , and go in left and right sub parts , if its a substring then we return 0 , but how will we combine subparts ? I am confused . pseudo code will be helpful

[@saranshpathak3795]

Its quite similar to climbing stairs ,just with palindromic twist...so smooth explanation by striver.

[@priyanshkumar17]

I agree!!!

[@ujjalsaha428]

As always "understood" ❤️, just got confused on the Time Complexity Part 😵!

[@SelvaArumugam-xq5mf]

I had been following dp after completing yours recursion series and I remeber solving this now i solved this on my own before seing the vedio it was kindoff a cake walk without any errors

[@sathvikmalgikar2842]

sir you are great thank you so much for helping students with this gold level content. very easy to grasp and fun to solve !

[@ris_colid325]

What are the particular features of this problem over MCM problem that allow using this front partition approach here ?,because it was not possible for MCM problem .There we had the O(N^3) solution there considering all partitions and then solving both left and right sides of the partition as separate subproblems.

[@AkshatMaheshwari-wm1yg]

same question

[@rishabhgupta9846]

understood ,able to solve by myself

[@shyamsundersrd]

Thanks Alot master. Understood. 👏

[@1tav0]

This was so smooth, us

[@piku9712]

Amazing. Thanks for this!!

[@shantipriya370]

wonderful explanation

[@Hrushi_2000]

Understood. Thankyou Sir

[@cameye9]

Sir what about timeComplexity of checking isPalindrome is O(n) not Including in total TimeComplexity.

[@prathmeshadsod629]

🤩u made dp so simple bro Thanks ... Can you make video on Travelling Salesperrson using DP

[@ratinderpalsingh5909]

Understood, sir. Thank you very much.

[@MOHDSALMAN-sj2zu]

Those who are getting TLE. Try to memorize the palindrome check too. Take a reference of below code snipped: private int[][] dpPalin; private boolean isPalindrome(String s, int i, int j) { if(i>=j) return true; if(dpPalin[i][j] != 0) return dpPalin[i][j] == 1; else dpPalin[i][j] = (s.charAt(i) == s.charAt(j) && isPalindrome(s, i+1, j-1)) ? 1 : -1; return dpPalin[i][j] == 1; }

[@prashudeshmukh7902]

still getting tle

[@devanshbatra308]

@@prashudeshmukh7902 try putting & before the "s" in the isPalindrome() function.

[@anshulgoel1940]

How to evaluate where to use MCM and where to use front partitioning. Somehow I have a hunch we can solve all the MCM problems using front partitioning. Please suggest.

[@10minutes_cs]

yes , please someone explain , I also have same query .

[@cinime]

Understood!! Thank you soooooo much as always!!!

[@lakshaysharma6550]

UNDERSTOOD!!!

[@ashutoshgupta4516]

Tried solving it in Leetcode, found TLE with a long string with a's and 2 b's in the middle, is anyone else seeing the same error as well?

[@princechaurasia7624]

yes

[@mathematics7746]

@@princechaurasia7624 pass by reference to avoid tle

[@ayushidalal5488]

@@mathematics7746 It worked. Thanks!!

[@mathematics7746]

@@ayushidalal5488 wlcm

[@AyushKumar-ty4cl]

What is the time complexity of memoization & tabulation solutions?? Is it O(n^3) ??

[@shivamkumar5857]

yes

[@aryankumar3018]

Understood

[@csea_37_shayoribhowmick53]

Thank you so much

[@undefined_exception_0]

Thanks Striver for another amazing video #understood Optimized O(N^2) approach int minCuts(string& str) { int n = str.size(); // precomputing every substring is palindrome or not vector isPalindrome(n , vector (n , false)); for(int i=n-1 ; i>=0 ; i--){ for(int j=i ; j

[@shashankvashishtha4454]

understood

[@aryanraj4088]

Great Explanation ! Thank you for the video !! This solution is giving TLE on LeetCode !!

[@kunjthakkar8725]

you have to pass string as pass by reference.

[@vibhanshugarg3603]

class Solution { public: bool isPalin(int i, int j, string& s){ while(i

[@surajbhardwaj2599]

@@kunjthakkar8725 thanks bro!

[@arihantjammar8888]

Understood 😊

[@satyampande684]

understood!!

[@nimmalavishnu3044]

time complexity for tabulation solution o(n3)

[@MOHDSALMAN-sj2zu]

It will be O(n^2) if you precompute palindrome check too.

[@JE_Dinesh]

@@MOHDSALMAN-sj2zu Otherwise it will be 0(n4) right? if we consider a 1 single palindrome string then for 1st forloop it will be n 2nd for loop n and for ispalindrome function will be n2 right(if i=0 then for each j from 0 to n we have to do palindrome check)?

[@nanda_8]

@@MOHDSALMAN-sj2zu even If we precompute, That precomputation will end up taking n^3

[@ganeshkamath89]

Thanks Striver. Understood.

[@samyakjain7422]

understood!!!!

[@lakshyabansal2542]

Understood Thanks man!

[@ayankhan-xh8zt]

understood sir

[@ankitpandey7262]

Understood ✌

[@yeswanthh5068]

Understood 🙂

[@NARUTOUZUMAKI-bk4nx]

understood🙏

[@mathematics7746]

can we optimized its space to only two variable????

[@RahulKumar-be3lq]

Understood 😀

[@siddharth794]

Why can't we go till n-1 to remove the extra partition at last

[@akashsahu2571]

yes

[@AmarjeetKumar-to9ub]

Thank You :)

[@harshvardhansingh7863]

thank you sir

[@AkshatMaheshwari-wm1yg]

Can anyone tell me why are we using front partitioning here and not normal partitioning. Reply is highly appreciated!

[@CodeRocks-z6g]

i think we can use previous approach but that will give mle thats why we move to dp

[@vxbsjisjjdjjdn]

I tried almost same approach but giving wrong answer, can anyone tell what is wrong in my code? CODE: class Solution: def minCut(self, s: str) -> int: def is_palindrome(sub): return sub == sub[::-1] def f(i, prev): if i == n: return 0 take = float('inf') notTake = f(i + 1, prev) if is_palindrome(s[prev:i + 1]): take = 1 + f(i + 1, i + 1) return min(take, notTake) n = len(s) return f(0, 0)

[@tikshavarshney213]

Understood !

[@giraffe4375]

Thanks striver

[@Harshit126]

Understood, thanks

[@adityadixit7973]

understood😁😁

[@ashishrana-jw8ye]

understood

[@iamnoob7593]

US striver

[@Hello-ro6hr]

UNDERSTOOD ...

[@aditithakur6226]

Understood Sir :)

[@parshchoradia9909]

Understood Sir!

[@mrityunjoybarman9098]

Understood

[@srikanthbankuru9557]

understood dude :)

[@harshdasila6680]

Leetcode giving TLE on all 3 solutions

[@VaibhavSharma-mm3wv]

Memoization passed

[@rechinraj111]

@@VaibhavSharma-mm3wv can u plz paste ur solution here? Actually its giving TLE in leetcode.

[@rechinraj111]

finally it worked. Just changed isPalindrome() method from iterative to recursive. Now in leetcode it passed.

[@optimusprime5040]

Memoize both main function and palindrome checking function XD

[@vibhanshugarg3603]

passing by reference worked well!

[@abhayrai1724]

understood 😁

[@arsyaswanth5]

Understood sir!!!!

[@manasranjanmahapatra3729]

Understood💯

[@maheshjindal2622]

Understoooood

[@anshumangupta1001]

Understood.

[@brokegod5871]

This approach will fail in leetcode because of the fact that this logic makes a cut when it finds a fresh palindrome, it doesn't maintain the flow if a palindrome is ongoing. For example, if you have "cdd", by his logic you will get answer as 2 because the cut first happens at c, then cd is invalid so goes to d in which another cut happens for one d, and then the last cut at last d which is extra for which we do minus one at the end but the answer is actually just one cut because c and "dd" itself is a palindrome, but his code cuts "dd" into two separate d's. You need to first precompute the presence of all possible palindromes and then the code is the same but this time we check from the precomputed array if the string being examined is already a palindrome or not. This is the memoised code, you can tabulate it easily. class Solution { public: bool isPalindrome(string &s, int i, int j, vector &dp) { if(i>=j) return true; if(dp[i][j]!=-1) return dp[i][j]; if(s[i]==s[j]) return dp[i][j] = isPalindrome(s, i+1, j-1, dp); else return dp[i][j] = false; } int solve(int i, int n, string &s, vector &dp, vector &dp2) { if(i==n) return 0; if(dp2[i]!=-1) return dp2[i]; string temp=""; int ans = 1e9; for(int j=i;j

[@I_Anupam_Pandey]

understand

[@suhaanbhandary4009]

Understood!!

[@piyushgaur6975]

Why Gap Strategy is giving TLE on this question?? //Gap Startegy ----> bool isPalindromic(string &s, int i, int j){ while(i

[@bhavya8608]

understoood!!!!

[@rayyansyed2998]

"us"

[@475_nehakaushik5]

understoood

[@subodhkasaudhaniitk796]

Understood :)))

[@sameersahu4569]

Understood!!!

[@sathyakrishnanthirunavukka7908]

US

[@harishseepathi9459]

striver getting tle in leetcode

[@Lucifer0872]

❤️❤️❤️❤️

[@KartikRai-YrIDDCompSciEngg]

Giving TLE on leetcode

[@rohalkurup1350]

Recursive solution with memoization accepted in leetcode , PSB code class Solution { public int minCut(String s) { int dp[] = new int[s.length()]; Arrays.fill(dp,-1); return solve(0,s.length(),s,dp); } public int solve(int i,int n,String s,int []dp) { if(i==n || isPalindrome(s,i,n-1)) return 0; if(dp[i]!=-1) return dp[i]; int minCost = 9999; for(int j=i;j

[@priyanshkumar17]

Tabulation code for leetcode : class Solution { private: bool isPalindrome(string &s, int i, int j){ while(i < j){ if(s[i] != s[j]) return false; i++; j--; } return true; } public: int minCut(string s) { int n= s.length(); vector dp(n + 1, 0); for(int i = n - 1; i >= 0; i--){ int minCuts = INT_MAX; for(int j = i; j < n; j++){ if(isPalindrome(s, i, j)){ int cuts = 1 + dp[j + 1]; minCuts = min(minCuts, cuts); } } dp[i] = minCuts; } return dp[0] - 1; } };

[@harshjain8596]

UnderStood - Below is the java code with pallindrome array public int minCut(String s) { int n = s.length(); boolean[][] dp = new boolean[n][n]; for(int jump=0;jump

[@codingp110]

US!

[@AB-tp9eg]

"US"

[@RohitKumar-dy2gc]

US

[@divyatejaswinivengada6368]

US!!

[@MicahJosephBIT]

In leetcode when I am trying to submit it's giving me Memory Limit Exceeded. What to do?

[@light-ln3hy]

Pass your string via reference....use '&' operator

[@meetsoni1938]

US 🔥🔥

[@sakshimishra1491]

Use this updated code for java as test cases have been updated on leetcode and above memoization solution gives tle: class Solution { public int minCut(String s) { int[] cut = new int[s.length()]; boolean[][] p = new boolean[s.length()][s.length()]; for (int i = 0; i < s.length(); i++) { int minCut = i; for (int j = 0; j

[@tusharnain6652]

// N^2 time and N^2 space solution C++ void isPalinUtility(const string &s, vector &isPalin) { int n = s.size(); for (int i = n - 1; i >= 0; i--) { for (int j = i; j < n; j++) { if (i == j) // for single character //base case ya' know isPalin[i][j] = true; else if (i + 1 == j) // for 2 size string //kinda like base case isPalin[i][j] = s[i] == s[j] ? true : false; else { if (s[i] == s[j]) isPalin[i][j] = isPalin[i + 1][j - 1]; else isPalin[i][j] = false; } } } } int palindromicPartition(string str) { int n = str.size(); vector dp(n + 1); dp[n] = 0; vector isPalin(n, vector(n, false)); isPalinUtility(str, isPalin); for (int i = n - 1; i >= 0; i--) { int min_result = INT_MAX; for (int k = i; k < n; k++) { if (isPalin[i][k]) { int temp = 1 + dp[k + 1]; if (temp < min_result) min_result = temp; } } dp[i] = min_result; } return dp[0] - 1; }

[@sudarshanwadajkar8323]

us

[@roushansingh2945]

us