Skip to content

2472. Maximum Number of Non-overlapping Palindrome Substrings

Difficulty Topics

Description

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.

 

Example 1:

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

maximum-number-of-non-overlapping-palindrome-substrings.py
class Solution:
    def maxPalindromes(self, s: str, k: int) -> int:
        N = len(s)
        pal = [[False] * N for _ in range(N)]

        for i in range(N - 1, -1, -1):
            for j in range(i, N):
                pal[i][j] = s[i] == s[j] and (j - i + 1 < 3 or pal[i + 1][j - 1])

        dp = [0] * (N + 1)

        for i in range(N - 1, -1, -1):
            dp[i] = dp[i + 1]
            for j in range(i + k - 1, N):
                if pal[i][j]:
                    dp[i] = max(dp[i], 1 + dp[j + 1])

        return dp[0]