Maximum Number of Non-overlapping Palindrome Substrings

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 themaximum number of substrings in an optimal selection.

A substring is a contiguous sequence of characters within a string.

Examples

Example 1

Input: s = "abaccdbbd", k = 3
Output: 2
Explanation: We can select the substrings underlined in s = "_**aba**_ cc _**dbbd**_ ". 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

Method 1 – Dynamic Programming + Greedy

Intuition

We want to select the maximum number of non-overlapping palindromic substrings of length at least k. We can use dynamic programming to precompute all palindromic substrings, then greedily select the earliest non-overlapping palindromes.

Approach

1. Precompute a 2D boolean array is_pal[i][j] indicating if s[i:j+1] is a palindrome.
2. For each possible substring of length at least k, mark it as a palindrome if it is.
3. Use a greedy approach: start from the beginning, and whenever a palindrome of length at least k is found, select it and jump to the end of that substring.
4. Count the number of such selections.

Code

C++

class Solution {
public:
    int maxPalindromes(string s, int k) {
        int n = s.size(), ans = 0, i = 0;
        vector<vector<bool>> is_pal(n, vector<bool>(n, false));
        for (int len = 1; len <= n; ++len) {
            for (int l = 0; l + len - 1 < n; ++l) {
                int r = l + len - 1;
                if (s[l] == s[r] && (len <= 2 || is_pal[l+1][r-1]))
                    is_pal[l][r] = true;
            }
        }
        while (i <= n - k) {
            bool found = false;
            for (int j = i + k - 1; j < n; ++j) {
                if (is_pal[i][j]) {
                    ans++;
                    i = j + 1;
                    found = true;
                    break;
                }
            }
            if (!found) i++;
        }
        return ans;
    }
};

Go

func maxPalindromes(s string, k int) int {
    n := len(s)
    isPal := make([][]bool, n)
    for i := range isPal {
        isPal[i] = make([]bool, n)
    }
    for l := 1; l <= n; l++ {
        for i := 0; i+l-1 < n; i++ {
            j := i + l - 1
            if s[i] == s[j] && (l <= 2 || isPal[i+1][j-1]) {
                isPal[i][j] = true
            }
        }
    }
    ans, i := 0, 0
    for i <= n-k {
        found := false
        for j := i+k-1; j < n; j++ {
            if isPal[i][j] {
                ans++
                i = j+1
                found = true
                break
            }
        }
        if !found {
            i++
        }
    }
    return ans
}

Java

class Solution {
    public int maxPalindromes(String s, int k) {
        int n = s.length(), ans = 0, i = 0;
        boolean[][] isPal = new boolean[n][n];
        for (int len = 1; len <= n; len++) {
            for (int l = 0; l + len - 1 < n; l++) {
                int r = l + len - 1;
                if (s.charAt(l) == s.charAt(r) && (len <= 2 || isPal[l+1][r-1]))
                    isPal[l][r] = true;
            }
        }
        while (i <= n - k) {
            boolean found = false;
            for (int j = i + k - 1; j < n; j++) {
                if (isPal[i][j]) {
                    ans++;
                    i = j + 1;
                    found = true;
                    break;
                }
            }
            if (!found) i++;
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun maxPalindromes(s: String, k: Int): Int {
        val n = s.length
        val isPal = Array(n) { BooleanArray(n) }
        for (len in 1..n) {
            for (l in 0..n-len) {
                val r = l + len - 1
                if (s[l] == s[r] && (len <= 2 || isPal[l+1][r-1]))
                    isPal[l][r] = true
            }
        }
        var ans = 0
        var i = 0
        while (i <= n - k) {
            var found = false
            for (j in i + k - 1 until n) {
                if (isPal[i][j]) {
                    ans++
                    i = j + 1
                    found = true
                    break
                }
            }
            if (!found) i++
        }
        return ans
    }
}

Python

class Solution:
    def maxPalindromes(self, s: str, k: int) -> int:
        n = len(s)
        is_pal = [[False]*n for _ in range(n)]
        for length in range(1, n+1):
            for l in range(n-length+1):
                r = l + length - 1
                if s[l] == s[r] and (length <= 2 or is_pal[l+1][r-1]):
                    is_pal[l][r] = True
        ans, i = 0, 0
        while i <= n - k:
            found = False
            for j in range(i+k-1, n):
                if is_pal[i][j]:
                    ans += 1
                    i = j + 1
                    found = True
                    break
            if not found:
                i += 1
        return ans

Rust

impl Solution {
    pub fn max_palindromes(s: String, k: i32) -> i32 {
        let n = s.len();
        let s = s.as_bytes();
        let k = k as usize;
        let mut is_pal = vec![vec![false; n]; n];
        for len in 1..=n {
            for l in 0..=n-len {
                let r = l + len - 1;
                if s[l] == s[r] && (len <= 2 || is_pal[l+1][r-1]) {
                    is_pal[l][r] = true;
                }
            }
        }
        let mut ans = 0;
        let mut i = 0;
        while i + k <= n {
            let mut found = false;
            for j in i+k-1..n {
                if is_pal[i][j] {
                    ans += 1;
                    i = j + 1;
                    found = true;
                    break;
                }
            }
            if !found {
                i += 1;
            }
        }
        ans
    }
}

TypeScript

class Solution {
    maxPalindromes(s: string, k: number): number {
        const n = s.length;
        const isPal: boolean[][] = Array.from({length: n}, () => Array(n).fill(false));
        for (let len = 1; len <= n; len++) {
            for (let l = 0; l + len - 1 < n; l++) {
                const r = l + len - 1;
                if (s[l] === s[r] && (len <= 2 || isPal[l+1][r-1]))
                    isPal[l][r] = true;
            }
        }
        let ans = 0, i = 0;
        while (i <= n - k) {
            let found = false;
            for (let j = i + k - 1; j < n; j++) {
                if (isPal[i][j]) {
                    ans++;
                    i = j + 1;
                    found = true;
                    break;
                }
            }
            if (!found) i++;
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n^2), for palindrome DP and greedy selection.
• 🧺 Space complexity: O(n^2), for the DP table.