We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Non-overlapping Palindrome Substrings

Difficulty: Hard

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

Key Insights

  • Palindromes are strings that read the same forwards and backwards.
  • Non-overlapping substrings must be selected such that they do not share any characters.
  • A dynamic programming approach can be useful for identifying all palindromic substrings.
  • A greedy approach may be employed to select the maximum number of valid substrings based on their starting positions.

Space and Time Complexity

Time Complexity: O(n^2) where n is the length of the string s, due to the palindrome checking. Space Complexity: O(n) for storing the valid palindromic substrings.

Solution

To solve this problem, we can use a dynamic programming approach to identify all substrings of s that are palindromes. We will create a 2D array dp where dp[i][j] indicates whether the substring from index i to j is a palindrome.

  1. Initialize a list to collect all palindromic substrings of length at least k.
  2. Use a nested loop to fill the dp table:
    • For each character, check for odd-length and even-length palindromes.
    • If a palindrome of length at least k is found, add it to our list.
  3. Use a greedy approach to select the maximum number of non-overlapping palindromic substrings from the list:
    • Sort the substrings by their ending index.
    • Iterate through the list and count how many can be selected without overlapping.

This approach ensures that we efficiently find and count the valid substrings.

Code Solutions

def maxPalindromicSubstrings(s: str, k: int) -> int:
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    palindromes = []

    # Fill dp table
    for length in range(1, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and (length <= 2 or dp[i + 1][j - 1]):
                dp[i][j] = True
                if length >= k:
                    palindromes.append((i, j))

    # Greedily select non-overlapping palindromes
    palindromes.sort(key=lambda x: x[1])  # sort by end index
    count = 0
    last_end = -1

    for start, end in palindromes:
        if start > last_end:
            count += 1
            last_end = end

    return count
← Back to All Questions