# Palindromic String Partition | Variation of MCM

Hey, Guys, I watched Video From Aditya Verma series and then Write Optimise Code for
Palindromic String Partition but it is giving me TLE.

My leetcode solution which is giving TLE

I’m not sure why you’re getting TLE. It looks like your code is \mathcal O(n^2). Did you try a bottom up approach?

Here is my \mathcal O(n^2) implementation, but with a 1D dp.

Code
class Solution {
public:
int minCut(string s) {
int n = s.size();
vector<vector<bool>> ispal(n, vector<bool>(n));
for(int i = 0; i < n; i++) ispal[i][i] = 1;
for(int i = 1; i < n; i++) ispal[i][i - 1] = 1;
for(int p = 1; p < n; p++) {
for(int i = 0; i < n - p; i++) {
int j = i + p;
if(s[i] == s[j]) ispal[i][j] = ispal[i + 1][j - 1];
}
}
vector<int> dp(n, INT_MAX);
for(int i = 0; i < n; i++) {
for(int j = 0; j <= i; j++) {
if(ispal[j][i]) {
if(j == 0)
dp[i] = min(dp[i], 0);
else
dp[i] = min(dp[i], 1 + dp[j - 1]);
}
}
}
return dp[n-1];
}
};

2 Likes

Actually I don’t understood the bottom up dp for this problem i,e., I decided to solve using top down approach.
I also unable to figure out why its giving me TLE.

Argh. I see why. Pass your string by reference and not by value. If you pass it by value, the string is copied for each and every call, which is another \mathcal O(n). So the overall runtime is \mathcal O(n^3).

2 Likes

Can you explain me why this coping takes O(N) time complexity.

Actually I tried using call by reference but also giving TLE. What to do now sir!!!

To copy a string, you have to copy character by character, which is \mathcal O(n).

Try with a global string for the given string? (There isn’t much difference, but I don’t see any other reason for TLE).

1 Like

Sorry to disturb but open this brother and see this

Um, I don’t think people can see your submission. It says Error 404 when I open it.

1 Like

I am sorry brother, But this link is opening in me correctly. one second I bind the code and give it to you.