LeetCode Entry

2472. Maximum Number of Non-overlapping Palindrome Substrings

15.09.2026 hard 2026 kotlin rust

Max palindrome substrings at least k length

2472. Maximum Number of Non-overlapping Palindrome Substrings hard substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1483

Problem TLDR

Max palindrome substrings at least k length

Intuition

Greedily choose the smallest palindrome ending with current position.

Approach

• can be done recursively
• possible sizes can be just two: k and k+1

Complexity

• Time complexity: \(O(nk)\)

• Space complexity: \(O(1)\)

Code

    fun maxPalindromes(s: String, k: Int): Int =
        s.indices.find { i ->
            (max(0,i-k)..i-k+1).any {l->(0..k/2).all{s[l+it]==s[i-it]}}
        }?.let { 1 + maxPalindromes(s.drop(it + 1), k) } ?: 0

    pub fn max_palindromes(s: String, k: i32) -> i32 {
        let u = k as usize; (0..s.len())
            .find(|&i| (i..=i + 1).any(|x| x >= u && s[x - u..=i].bytes().eq(s[x - u..=i].bytes().rev())))
            .map_or(0, |i| 1 + Self::max_palindromes(s[i + 1..].into(), k))
    }