2472. Maximum Number of Non-overlapping Palindrome Substrings LeetCode Solution
In this guide, you will get 2472. Maximum Number of Non-overlapping Palindrome Substrings LeetCode Solution with the best time and space complexity. The solution to Maximum Number of Non-overlapping Palindrome Substrings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Number of Non-overlapping Palindrome Substrings
You are given a string s and a positive integer k.
Select a set of non-overlapping substrings from the string s that satisfy the following conditions:
The length of each substring is at least k.
Each substring is a palindrome.
Return the maximum number of substrings in an optimal selection.
A substring is a contiguous sequence of characters within a string.
Example 1:
Input: s = “abaccdbbd”, k = 3
Output: 2
Explanation: We can select the substrings underlined in s = “abaccdbbd”. Both “aba” and “dbbd” are palindromes and have a length of at least k = 3.
It can be shown that we cannot find a selection with more than two valid substrings.
Example 2:
Input: s = “adbcda”, k = 2
Output: 0
Explanation: There is no palindrome substring of length at least 2 in the string.
Constraints:
1 <= k <= s.length <= 2000
s consists of lowercase English letters.
Complexity Analysis
Time Complexity: O(nk)
Space Complexity: O(n)
2472. Maximum Number of Non-overlapping Palindrome Substrings LeetCode Solution in C++
class Solution {
public:
int maxPalindromes(string s, int k) {
const int n = s.length();
// dp[i] := the maximum number of substrings in the first i chars of s
vector<int> 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;
}
}; /* code provided by PROGIEZ */
2472. Maximum Number of Non-overlapping Palindrome Substrings LeetCode Solution in Java
class Solution {
public int maxPalindromes(String s, int k) {
final int n = s.length();
// dp[i] := the maximum number 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;
}
} // code provided by PROGIEZ
2472. Maximum Number of Non-overlapping Palindrome Substrings LeetCode Solution in Python
class Solution:
def maxPalindromes(self, s: str, k: int) -> int:
n = len(s)
# dp[i] := the maximum number of substrings in the first i chars of s
dp = [0] * (n + 1)
def isPalindrome(l: int, r: int) -> bool:
"""Returns True is s[i..j) is a palindrome."""
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] # code by PROGIEZ
