Maximum Number of Non-overlapping Palindrome Substrings

Medium
1045.

Maximum Number of Non-overlapping Palindrome Substrings

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.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var maxPalindromes = function(s, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.

Hints for Maximum Number of Non-overlapping Palindrome Substrings

  1. Hint 1

    Only lengths k and k + 1 ever need to be considered.

  2. Hint 2

    Any longer palindrome contains a centred palindrome of length exactly k or k + 1 — and a shorter piece leaves more room for the rest.

  3. Hint 3

    So dp[i] = the best answer for the prefix of length i: skip the character, or close a palindrome of length k or k + 1 here.

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

  1. Fill isPal[i][j] with the usual interval recurrence.
  2. For each prefix length i, start from dp[i-1].
  3. 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.
  4. 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]

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