LeetCode 2472 - Maximum Number of Non-overlapping Palindrome Substrings

Difficulty: 🔴 Hard
Topics: Two Pointers, String, Dynamic Programming, Greedy

Solution

Problem Understanding

The problem asks us to find the maximum number of non-overlapping palindrome substrings in a given string s such that each substring has a length of at least k. In other words, we are looking to segment the string into valid palindromic blocks, where no two selected blocks overlap and each block is long enough. The input is a string s of lowercase English letters and a positive integer k. The output is a single integer representing the maximum number of such non-overlapping palindromic substrings.

Constraints tell us that the string length can be up to 2000, which means any solution with worse than O(n²) time complexity could be too slow. Edge cases to consider include strings where no substring of length ≥ k is a palindrome, strings where every character is the same, and cases where k is equal to the length of the string.

Key points to note:

Substrings must be contiguous.
Substrings cannot overlap.
Each palindrome must have length at least k.

This makes the problem a combination of palindrome detection and interval selection, hinting at dynamic programming or greedy approaches.

Approaches

The brute-force approach would involve generating all possible substrings of length ≥ k, checking if each is a palindrome, and then attempting all combinations of non-overlapping selections. This approach is correct but extremely inefficient because there are O(n²) substrings, and for each substring checking for palindrome could take O(n), leading to O(n³) complexity. Furthermore, trying all combinations of non-overlapping substrings would be exponential in the number of substrings.

The key observation for an optimal solution is that we only need to know which substrings are palindromes, then use a greedy or dynamic programming approach to select the maximum number of non-overlapping intervals. Precomputing palindrome substrings using a center expansion method or a DP table allows us to quickly check for palindromes. Once we have this, we can iterate from left to right and always select the next valid palindrome that starts after the previous one ends. This works because choosing the earliest-ending palindrome gives the best chance for maximizing the count (classic interval scheduling logic).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(n²)	Generate all substrings ≥ k, check palindrome, enumerate all combinations
Optimal	O(n²)	O(n²)	Precompute palindromes using DP, then greedy interval selection

Algorithm Walkthrough

Precompute palindromes: Create a 2D boolean array is_palindrome[i][j] indicating if the substring s[i:j+1] is a palindrome. Use the standard DP formula: is_palindrome[i][j] = (s[i] == s[j]) and (j-i < 3 or is_palindrome[i+1][j-1]). This allows O(1) palindrome queries.
Initialize variables: Set a variable last_end = -1 to track the end of the last selected palindrome and count = 0 to accumulate the number of selected palindromes.
Iterate through the string: For each possible start index i in the string, check all substrings s[i:j+1] where j >= i + k - 1. If the substring is a palindrome and i > last_end, select it, increment count, and update last_end = j.
Return the result: After iterating through the string, return count as the maximum number of non-overlapping palindromes.

Why it works: By precomputing all palindromes, we reduce repeated computations. Selecting the earliest-ending palindrome ensures that we leave as much space as possible for future palindromes, which is a greedy strategy known to be optimal in interval selection problems.

Python Solution

class Solution:
    def maxPalindromes(self, s: str, k: int) -> int:
        n = len(s)
        # DP table for palindrome checks
        is_palindrome = [[False] * n for _ in range(n)]
        
        for end in range(n):
            for start in range(end + 1):
                if s[start] == s[end] and (end - start < 3 or is_palindrome[start + 1][end - 1]):
                    is_palindrome[start][end] = True
        
        count = 0
        last_end = -1
        
        for start in range(n):
            for end in range(start + k - 1, n):
                if is_palindrome[start][end] and start > last_end:
                    count += 1
                    last_end = end
                    break
        
        return count

This implementation first fills a DP table to know which substrings are palindromes. Then it iterates left to right, greedily selecting the first valid palindrome that does not overlap with the previous selection. The inner loop breaks immediately after a selection to avoid overlap, ensuring maximal count.

Go Solution

func maxPalindromes(s string, k int) int {
    n := len(s)
    isPalindrome := make([][]bool, n)
    for i := range isPalindrome {
        isPalindrome[i] = make([]bool, n)
    }
    
    for end := 0; end < n; end++ {
        for start := 0; start <= end; start++ {
            if s[start] == s[end] && (end-start < 3 || isPalindrome[start+1][end-1]) {
                isPalindrome[start][end] = true
            }
        }
    }
    
    count := 0
    lastEnd := -1
    
    for start := 0; start < n; start++ {
        for end := start + k - 1; end < n; end++ {
            if isPalindrome[start][end] && start > lastEnd {
                count++
                lastEnd = end
                break
            }
        }
    }
    
    return count
}

The Go solution mirrors the Python logic. The main differences are explicit slice initialization and the use of make for the DP table. Go slices handle boolean arrays efficiently, and the algorithm logic remains identical.

Worked Examples

Example 1: s = "abaccdbbd", k = 3

Palindromes of length ≥ 3: "aba" at [0:2], "acc" invalid, "dbbd" at [5:8].
Iteration:
Start=0, pick "aba", last_end=2, count=1.
Start=5, pick "dbbd", last_end=8, count=2.
Result: 2.

Example 2: s = "adbcda", k = 2

No palindrome substring of length ≥ 2 exists.
Result: 0.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Filling the DP table takes O(n²) and the greedy selection loop is also O(n²) in worst case
Space	O(n²)	The DP table storing palindrome status for all substrings requires O(n²) space

The complexity is dominated by the DP table construction. Iterating over palindromes afterward is bounded by O(n²) but in practice faster due to the break after selection.

Test Cases

# Basic examples
assert Solution().maxPalindromes("abaccdbbd", 3) == 2  # Example 1
assert Solution().maxPalindromes("adbcda", 2) == 0     # Example 2

# Edge cases
assert Solution().maxPalindromes("aaaaa", 1) == 5      # All single letters are palindromes
assert Solution().maxPalindromes("aaaaa", 2) == 2      # Overlapping prevention reduces count
assert Solution().maxPalindromes("abcde", 2) == 0      # No palindrome of length >= 2
assert Solution().maxPalindromes("racecarannakayak", 3) == 3  # Multiple palindromes
assert Solution().maxPalindromes("a", 1) == 1          # Single character
assert Solution().maxPalindromes("a", 2) == 0          # k greater than length

Test	Why
`"abaccdbbd", 3`	Validates selecting multiple non-overlapping palindromes
`"adbcda", 2`	Validates no palindromes exist
`"aaaaa", 1`	Tests minimal palindrome length of 1 and multiple selections
`"aaaaa", 2`	Tests overlapping prevention logic
`"abcde", 2`	Ensures no false positives for palindromes
`"racecarannakayak", 3`	Tests multiple palindromes in string
`"a", 1`	Single-character palindrome
`"a", 2`	k exceeds string length

Edge Cases

1. No palindrome of required length: If k is greater than any possible palindrome in s, the algorithm should correctly return 0. Our DP approach ensures that only substrings of length ≥ k are considered.

2. Entire string is a palindrome: If the entire string is a palindrome and `k <= len(s