##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2472.html

# 2472. Maximum Number of Non-overlapping Palindrome Substrings

• Difficulty: Hard.
• Related Topics: String, Dynamic Programming.
• Similar Questions: Longest Palindromic Substring, Palindrome Partitioning, Palindrome Partitioning II, Palindrome Partitioning III, Maximum Number of Non-Overlapping Substrings, Palindrome Partitioning IV.

## Problem

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.

## Solution (Java, C++, Python)

• class Solution {
private boolean[][] dp;
private int[] f;
private String s;
private int n;
private int k;

public int maxPalindromes(String s, int k) {
n = s.length();
f = new int[n];
this.s = s;
this.k = k;
dp = new boolean[n][n];
for (int i = 0; i < n; ++i) {
Arrays.fill(dp[i], true);
f[i] = -1;
}
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1];
}
}
return dfs(0);
}

private int dfs(int i) {
if (i >= n) {
return 0;
}
if (f[i] != -1) {
return f[i];
}
int ans = dfs(i + 1);
for (int j = i + k - 1; j < n; ++j) {
if (dp[i][j]) {
ans = Math.max(ans, 1 + dfs(j + 1));
}
}
f[i] = ans;
return ans;
}
}

• class Solution {
public:
int maxPalindromes(string s, int k) {
int n = s.size();
vector<vector<bool>> dp(n, vector<bool>(n, true));
vector<int> f(n, -1);
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1];
}
}
function<int(int)> dfs = [&](int i) -> int {
if (i >= n) return 0;
if (f[i] != -1) return f[i];
int ans = dfs(i + 1);
for (int j = i + k - 1; j < n; ++j) {
if (dp[i][j]) {
ans = max(ans, 1 + dfs(j + 1));
}
}
f[i] = ans;
return ans;
};
return dfs(0);
}
};

• 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


• func maxPalindromes(s string, k int) int {
n := len(s)
dp := make([][]bool, n)
f := make([]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]bool, n)
f[i] = -1
for j := 0; j < n; j++ {
dp[i][j] = true
}
}
for i := n - 1; i >= 0; i-- {
for j := i + 1; j < n; j++ {
dp[i][j] = s[i] == s[j] && dp[i+1][j-1]
}
}
var dfs func(int) int
dfs = func(i int) int {
if i >= n {
return 0
}
if f[i] != -1 {
return f[i]
}
ans := dfs(i + 1)
for j := i + k - 1; j < n; j++ {
if dp[i][j] {
ans = max(ans, 1+dfs(j+1))
}
}
f[i] = ans
return ans
}
return dfs(0)
}

func max(a, b int) int {
if a > b {
return a
}
return b
}


Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).