September 15Hard

Maximum number of non overlapping palindrome substrings

Two Pointers
String
Dynamic Programming
Greedy

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

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

Solution

class Solution:
    def maxPalindromes(self, s: str, k: int) -> int:
        n = len(s)
        is_palindrom = [[False] * n for _ in range(n)]

        for i in range(n):
            is_palindrom[i][i] = True
            if i != n - 1:
                is_palindrom[i][i+1] = s[i] == s[i + 1]
        
        for i in range(n - 1, -1, -1):
            for j in range(i + 2, n):
                if s[i] == s[j]:
                    if i + 1 < n:
                        is_palindrom[i][j] = is_palindrom[i + 1][j - 1]

        @cache
        def dp(i):
            if i > len(s) - k:
                return 0
            res = 0
            for j in range(i + k - 1, len(s)):
                if is_palindrom[i][j]:
                    res = max(res, 1 + dp(j+1))
            return max(res, dp(i+1))
        
        return dp(0)