Maximum Number of Non-overlapping Palindrome Substrings — LeetCode 2472 Python Solution

The 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.

Example

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.

Python solution

class Solution:
    def maxPalindromes(self, s: str, k: int) -> int:
        @cache
        def dfs(i):
            if i >= n:
                return 0
            ans = dfs(i + 1)
            for j in range(i + k - 1, n):
                if dp[i][j]:
                    ans = max(ans, 1 + dfs(j + 1))
            return ans

        n = len(s)
        dp = [[True] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                dp[i][j] = s[i] == s[j] and dp[i + 1][j - 1]
        ans = dfs(0)
        dfs.cache_clear()
        return ans

Complexity

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 2472. Maximum Number of Non-overlapping Palindrome Substrings is filed here because LeetCode tags it Two Pointers, which is the vocabulary this hub collects.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Related problems