# 2472. Maximum Number of Non-overlapping Palindrome Substrings    • Time: $O(nk)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Solution { public: int maxPalindromes(string s, int k) { const int n = s.length(); // dp[i] := max # of substrings in the first i chars of s vector dp(n + 1); // If a palindrome is a substring of another palindrome, then considering // the longer palindrome won't increase the number of non-overlapping // palindromes. So, we only need to consider the shorter one. Also, // considering palindromes with both k length and k + 1 length ensures that // we look for both even and odd length palindromes. for (int i = k; i <= n; ++i) { dp[i] = dp[i - 1]; // Consider palindrome with length k. if (isPalindrome(s, i - k, i - 1)) dp[i] = max(dp[i], 1 + dp[i - k]); // Consider palindrome with length k + 1. if (isPalindrome(s, i - k - 1, i - 1)) dp[i] = max(dp[i], 1 + dp[i - k - 1]); } return dp[n]; } private: // Returns true is s[i:j] is a palindrome. bool isPalindrome(const string& s, int l, int r) { if (l < 0) return false; while (l < r) if (s[l++] != s[r--]) return false; return true; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution { public int maxPalindromes(String s, int k) { final int n = s.length(); // dp[i] := max # of substrings in the first i chars of s int[] dp = new int[n + 1]; // If a palindrome is a subString of another palindrome, then considering // the longer palindrome won't increase the number of non-overlapping // palindromes. So, we only need to consider the shorter one. Also, // considering palindromes with both k length and k + 1 length ensures that // we look for both even and odd length palindromes. for (int i = k; i <= n; ++i) { dp[i] = dp[i - 1]; // Consider palindrome with length k. if (isPalindrome(s, i - k, i - 1)) dp[i] = Math.max(dp[i], 1 + dp[i - k]); // Consider palindrome with length k + 1. if (isPalindrome(s, i - k - 1, i - 1)) dp[i] = Math.max(dp[i], 1 + dp[i - k - 1]); } return dp[n]; } // Returns true is s[i:j] is a palindrome. private boolean isPalindrome(String s, int l, int r) { if (l < 0) return false; while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false; return true; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution: def maxPalindromes(self, s: str, k: int) -> int: n = len(s) # dp[i] := max # of substrings in the first i chars of s dp =  * (n + 1) # Returns True is s[i:j] is a palindrome. def isPalindrome(l: int, r: int) -> bool: if l < 0: return False while l < r: if s[l] != s[r]: return False l += 1 r -= 1 return True # If a palindrome is a subof another palindrome, then considering # the longer palindrome won't increase the number of non-overlapping # palindromes. So, we only need to consider the shorter one. Also, # considering palindromes with both k length and k + 1 length ensures that # we look for both even and odd length palindromes. for i in range(k, n + 1): dp[i] = dp[i - 1] # Consider palindrome with length k. if isPalindrome(i - k, i - 1): dp[i] = max(dp[i], 1 + dp[i - k]) # Consider palindrome with length k + 1. if isPalindrome(i - k - 1, i - 1): dp[i] = max(dp[i], 1 + dp[i - k - 1]) return dp[n]