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
Solution 1: Preprocessing + Memoization Search
First, preprocess the string s to get dp[i][j], which represents whether the substring s[i,..j] is a palindrome.
Then, define a function dfs(i) to represent the maximum number of non-overlapping palindrome substrings that can be selected from the substring s[i,..], i.e.,
\begin{aligned}
dfs(i) &= \begin{cases}
0, & i ≥ n \
max{dfs(i + 1), max_{j ≥ i + k - 1} {dfs(j + 1) + 1}}, & i < n
\end{cases}
\end{aligned}
The time complexity is O(n2), and the space complexity is O(n2). Here, n is the length of the string s.
PythonJavaC++Go
class Solution: def maxPalindromes(self, s: str, k: int) -> int: @cache def dfs(i): if i >= n: return 0 ans = dfs(i + 1) for j in range(i + k - 1, n): if dp[i][j]: ans = max(ans, 1 + dfs(j + 1)) return ans n = len(s) dp = [[True] * n for _ in range(n)] for i in range(n - 1, -1, -1): for j in range(i + 1, n): dp[i][j] = s[i] == s[j] and dp[i + 1][j - 1] ans = dfs(0) dfs.cache_clear() return ans(code-box)
