Maximum Number of Non-overlapping Palindrome Substrings — Medium Problem & Solution

Choose a set of non-overlapping substrings of s such that every chosen substring is a palindrome of length at least k.

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 <= 2000
s consists of lowercase English letters.

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 from dp[i-1].
For len = k and len = k + 1, if the window ending at i-1 is a palindrome, take dp[i-len] + 1 when 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 = 1 is 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]

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue