Dynamic Programming | Weekly Contest 319 | Maximum Number of Non-overlapping Palindrome Substrings

*************************************************
Interview Experiences Playlists -

*********************************************************************

Please show support and subscribe if you find the content useful.

[imraghavagr]

Great thought process explaination. Explained very well. Thanks!

[lalitpayla]

sir how non overlapping is preserved and if we consider "c" at 5th and 8th index then our substring will be overlapping according to our code.

[arunkumarrai]

class Solution {
int dp[2000];
public:
bool isPalindrome(string& s, int l, int r){
while(l<r){
if(s[l++] != s[r--]) return false;
}
return true;
}
int solve(string& s, int k, int idx){
if(idx >= s.size()) return 0;
if(dp[idx] != -1) return dp[idx];
int ans = 0;
for(int i=idx; i<s.size(); i++){
if(i-idx+1 >= k && isPalindrome(s, idx, i)){
int temp = 1 + solve(s, k, i+1);
ans = max(ans, temp);
}
}
int temp = solve(s, k, idx+1);
ans = max(ans, temp);
return dp[idx] = ans;
}
int maxPalindromes(string s, int k) {
memset(dp, -1, sizeof(dp));
return solve(s, k, 0);
}
};
How is this code accepted? Isn't the TC-O(N^3)?

[vamsimudaliar]

Such clear intuition ❤ Thank you !!
Can we solve this using sliding window too?. By precomputing number of palindromes present in pair (I, j) please suggest

[rohanreign]

Very good approach. But I couldn't understand the TC as why is is (N^2) + (N^2) and not (N^2) * (N^2). Is it so bcuz we're not passing a new dp array everytime we call but the same array for every call?

[a.nk.r]

What happened to the quality of the video? It's 360p only. Not able to see properly, but got the intuition. Appreciate the efforts 🤝🤝