2472. Maximum Number of Non-overlapping Palindrome Substrings
Explanation
To solve this problem, we can use dynamic programming to find all palindromes in the given string s. We can then use another dynamic programming approach to select non-overlapping palindromes that have a length of at least k. The idea is to iterate through the palindromes and keep track of the maximum number of non-overlapping palindromes found so far.
- Find all palindromes in the string
susing dynamic programming. - Use dynamic programming to select non-overlapping palindromes of length at least
k. - Keep track of the maximum number of non-overlapping palindromes found.
Time complexity: O(n^2) where n is the length of the input string s.
Space complexity: O(n^2) for storing the palindrome information.
class Solution {
public int countPalindromicSubstrings(String s, int k) {
int n = s.length();
boolean[][] isPalindrome = new boolean[n][n];
int count = 0;
// Find all palindromes
for (int len = 1; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
if (len == 1) {
isPalindrome[i][j] = true;
} else if (len == 2) {
isPalindrome[i][j] = (s.charAt(i) == s.charAt(j));
} else {
isPalindrome[i][j] = (s.charAt(i) == s.charAt(j) && isPalindrome[i + 1][j - 1]);
}
}
}
// Select non-overlapping palindromes of length at least k
int[] dp = new int[n];
for (int i = 0; i < n; i++) {
dp[i] = i > 0 ? dp[i - 1] : 0;
for (int j = 0; j <= i; j++) {
if (isPalindrome[j][i] && i - j + 1 >= k) {
dp[i] = Math.max(dp[i], (j > 0 ? dp[j - 1] : 0) + 1);
}
}
count = Math.max(count, dp[i]);
}
return count;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.