@@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 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..
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...
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.
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).
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.
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
@@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 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.
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
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.
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...
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
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
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.
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
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.
@@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)?
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)
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
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
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
// 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; }
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
whats wrng with this code giving WA in LC class Solution { public: bool isPalin(int i, int j, string s){ while(i>j){ if(s[i] != s[j]){ return false; } i++; j--; } return true; } int f(int i, int n, string str){ if(i == n) return 0; int min_cost = INT_MAX; for(int j = i;j
c++ solution working on leetcode int t[2001][2001]; bool stDp[2001][2001]; int solve(string st, int i, int j){ if(i>=j) return t[i][j]=0; if(t[i][j]!=-1) return t[i][j]; if(stDp[i][j]) return t[i][j] = 0; int ans = INT_MAX; for(int k=i; k
