Maximum Number of Non-overlapping Palindrome Substrings Solution
Maximum Number of Non-overlapping Palindrome Substrings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximum Number of Non-overlapping Palindrome Substrings is a medium coding problem on strings, dynamic programming and greedy, asked in Amazon, Google and Adobe interviews.
- Difficulty: Medium
- Topics: Strings, Dynamic Programming, Greedy
- Asked at: Amazon, Google, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Choose a set of non-overlapping substrings of s such that every chosen substring is a palindrome of length at least k.
Return the maximum number of substrings you can choose.
Example 1
Input: s = "abaccdbbd", k = 3
Output: 2
Explanation: `aba` and `dbbd`.
Example 2
Input: s = "aabbaa", k = 2
Output: 3
Explanation: `aa`, `bb` and `aa`.
Example 3
Input: s = "adbcda", k = 2
Output: 0
Explanation: No palindrome of length 2 or more exists.
Constraints
1 <= k <= s.length <= 2000s consists of lowercase English letters.
Hints for Maximum Number of Non-overlapping Palindrome Substrings
Hint 1
Only lengths
kandk + 1ever need to be considered.Hint 2
Any longer palindrome contains a centred palindrome of length exactly
kork + 1— and a shorter piece leaves more room for the rest.Hint 3
So
dp[i]= the best answer for the prefix of lengthi: skip the character, or close a palindrome of lengthkork + 1here.
How to solve Maximum Number of Non-overlapping Palindrome Substrings
Precompute a palindrome table, then run a prefix DP. dp[i] is the best count for s[0..i-1]: either dp[i-1] (this character joins nothing), or dp[i-len] + 1 when s[i-len..i-1] is a palindrome of length len, for len in {k, k+1}.
Approach
- Fill
isPal[i][j]with the usual interval recurrence. - For each prefix length
i, start fromdp[i-1]. - For
len = kandlen = k + 1, if the window ending ati-1is a palindrome, takedp[i-len] + 1when it is better. - Return
dp[n].
Why it works
Restricting to two lengths is the whole insight, and it is what turns an O(n³) enumeration into O(n²). A palindrome of length L > k + 1 has a palindromic core of length L - 2 at its centre; peeling pairs off until the length is k or k + 1 keeps it a palindrome, keeps it long enough, and frees characters at both ends for other choices — so no optimal answer is ever lost by only looking at the two shortest admissible lengths.
Complexity
- Time —
O(n²) - Space —
O(n²)
Pitfalls
- Checking every palindrome length is unnecessary and too slow at n = 2000.
- The substrings must not overlap, which is why the transition jumps back by the full length.
k = 1is allowed, and then every single character qualifies.
Reference solution
Python
def maxPalindromes(s: str, k: int) -> int:
n = len(s)
is_pal = [[False] * n for _ in range(n)]
for i in range(n):
is_pal[i][i] = True
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
is_pal[i][j] = s[i] == s[j] and (length == 2 or is_pal[i + 1][j - 1])
dp = [0] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i - 1]
for length in (k, k + 1):
if i - length >= 0 and is_pal[i - length][i - 1]:
dp[i] = max(dp[i], dp[i - length] + 1)
return dp[n]Java
public static int maxPalindromes(String s, int k) {
int n = s.length();
boolean[][] isPal = new boolean[n][n];
for (int i = 0; i < n; i++) isPal[i][i] = true;
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
isPal[i][j] = s.charAt(i) == s.charAt(j) && (len == 2 || isPal[i + 1][j - 1]);
}
}
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1];
for (int len = k; len <= k + 1; len++) {
if (i - len >= 0 && isPal[i - len][i - 1]) dp[i] = Math.max(dp[i], dp[i - len] + 1);
}
}
return dp[n];
}C++
int maxPalindromes(string s, int k) {
int n = (int) s.size();
vector<vector<bool>> isPal(n, vector<bool>(n, false));
for (int i = 0; i < n; i++) isPal[i][i] = true;
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
isPal[i][j] = s[i] == s[j] && (len == 2 || isPal[i + 1][j - 1]);
}
}
vector<int> dp(n + 1, 0);
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1];
for (int len = k; len <= k + 1; len++) {
if (i - len >= 0 && isPal[i - len][i - 1]) dp[i] = max(dp[i], dp[i - len] + 1);
}
}
return dp[n];
}JavaScript
var maxPalindromes = function(s, k) {
var n = s.length, i, j;
var isPal = [];
for (i = 0; i < n; i++) {
var row = [];
for (j = 0; j < n; j++) row.push(false);
isPal.push(row);
}
for (i = 0; i < n; i++) isPal[i][i] = true;
for (var len = 2; len <= n; len++) {
for (i = 0; i + len - 1 < n; i++) {
j = i + len - 1;
isPal[i][j] = s.charAt(i) === s.charAt(j) && (len === 2 || isPal[i + 1][j - 1]);
}
}
var dp = [];
for (i = 0; i <= n; i++) dp.push(0);
for (i = 1; i <= n; i++) {
dp[i] = dp[i - 1];
for (var L = k; L <= k + 1; L++) {
if (i - L >= 0 && isPal[i - L][i - 1] && dp[i - L] + 1 > dp[i]) dp[i] = dp[i - L] + 1;
}
}
return dp[n];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Dynamic Programming