Leetcode 1278. Palindrome Partitioning III Explanation and Code

Question explanation: 00:28
Approach: 03:00
Explanation of code: 07:08

Follow me on

[VaibhavSutar-xmcn]

very nice and smooth explanation in short.

[sajalkirtiman]

Good one. This solution can be visualize

[pulkitgupta]

are bhai aag laga di, mera toh laptop hi jal gaya

[faisals.]

Clean and small change

class Solution {
public:

int dp[101][101][101];


int minChange(string &s, int i, int j){
int cnt=0;



while(i<j){
if(s[i]!=s[j]) cnt++;
i++;j--;
}

return cnt;
}

int helper(string &s, int i, int j, int k){




if(k==1){

if(i>j) return

return minChange(s, i, j);

}


if(dp[i][j][k]!=-1) return dp[i][j][k];



string temp="";

int ans=j-i+1;

for(int start=i;start<=j;start++){
temp+=s[start];

int t = minChange(temp, 0, temp.length()-1);

ans = min(ans, helper(s, start+1, j, k-1)+t);


}

return dp[i][j][k]=ans;


}


int palindromePartition(string s, int k) {


// i can do this
memset(dp, -1, sizeof(dp));


return helper(s, 0, s.length()-1, k);

}
};

[ashutoshkumar]

in question it's said change characters then partition. But you have partitioned then changed characters. How did you come to this realisation?

[arungupta]

Do we really need this condition if(k <= 0) return 0; ?? because i think we never got into the situation where (k<=0)
if(start > end)
{
if(k <= 0)
return 0;
else
return
}

[akshatjain]

You are one of the best tutor I have ever seen.Please upload more tutorials.Don't worry for views now, you will surely grow in next few months. Also I want to ask you one question, I have done around 180 leetcode problems 112 medium 50 easy and rest hard, So should I do more hard problems now or should I foucs on core subjects. I have only 1 month to prepare for amazon.

[kunal_chand]

If anyone is wondering why he did the following :

for(int i=start; i<=end; i++)
{
int a = helper(s, 1, start, i, arr);
int b = helper(s, k-1, i+1, end, arr);

ans = min(ans, a+b);
}

Following is the visual iteration of the same :











At each iteration :
Part1 (a) :
Part2 (b) :

Part1 is recursively called for splitting it into 1 segments
Part2 is recursively called for splitting it into k-1 segments

In total, entire string gets split up in (1 + (k-1)) = k segments

a = number of conversions for part1
b = number of conversions for part2

a+b= number of conversions for entire string

In the next iteration part1 gets bigger & part2 gets smaller.