Description
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 <= 2000sconsists of lowercase English letters.
Solutions
This solution efficiently counts the maximum number of non-overlapping palindromes in string s where each palindrome has length k or k+1. The check function validates palindromes by comparing characters from both ends moving inward. The algorithm uses a greedy approach: for each ending position right, it first checks if the previous k characters form a palindrome, and if not, checks if the previous k+1 characters do; when a palindrome is found, it increments the count and updates start to the position after the palindrome to ensure no overlapping selections.
/** By Leetcode */
var maxPalindromes = function (s, k) {
const n = s.length;
let res = 0;
let start = 0;
const check = (left, right) => {
while (left < right && s[left] === s[right]) {
left++;
right--;
}
return left >= right;
};
for (let right = k - 1; right < n; right++) {
let left = right - k + 1;
if (left >= start && check(left, right)) {
res++;
start = right + 1;
continue;
}
left = right - k;
if (left >= start && check(left, right)) {
res++;
start = right + 1;
}
}
return res;
};