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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Non-overlapping Palindrome Substrings

Number: 2559

Difficulty: Hard

Paid? No

Companies: Oracle, SoFi, Salesforce, Walmart Labs, LinkedIn

Problem Description

Given a string s and a positive integer k, select a set of non-overlapping substrings from s such that each substring has length at least k and is a palindrome. Return the maximum number of substrings in an optimal selection. A substring is a contiguous sequence of characters within s.

Key Insights

  • We need substrings to be palindromes and their lengths must be at least k.
  • To maximize the count, it is beneficial to select the shortest valid palindrome starting at a given index.
  • A dynamic programming (DP) approach can precompute if any substring s[i...j] is a palindrome in O(n²) time.
  • A greedy strategy is then used to move through the string: at the current index, find the earliest ending palindrome (of length at least k) and jump to its end + 1.
  • This two-phase approach (DP for palindromic checks and greedy selection) ensures the selected substrings are non-overlapping and maximizes their count.

Space and Time Complexity

Time Complexity: O(n²) due to the DP precomputation for palindromic substrings. Space Complexity: O(n²) for storing the DP table.

Solution

The solution consists of two main parts. First, we precompute a DP table where dp[i][j] indicates whether the substring from index i to j is a palindrome. This is done by:

  1. Marking all single characters as palindromes.
  2. Checking substrings of length 2.
  3. Using the recurrence relation for longer substrings: a substring is a palindrome if its end characters match and the inner substring is also a palindrome.

Once the DP table is built, we iterate from left to right in the string using a greedy strategy. At each index i, we search for the smallest j (starting from i+k-1) such that dp[i][j] is true. When found, we count that substring and jump to index j+1 to ensure non-overlapping. If no such substring starts at i, we increment i by 1 and try again. This guarantees the maximum number of non-overlapping palindrome substrings is found.

Code Solutions

# Python solution with detailed comments

# Function to check maximum number of non-overlapping palindrome substrings
def max_palindrome_substrings(s, k):
    n = len(s)
    # Create DP table, dp[i][j] will be True if s[i...j] is a palindrome
    dp = [[False] * n for _ in range(n)]
    
    # Every single character is a palindrome
    for i in range(n):
        dp[i][i] = True
        
    # Check substrings of length 2
    for i in range(n - 1):
        dp[i][i + 1] = (s[i] == s[i + 1])
    
    # Fill the DP table for substrings of length >= 3
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            # s[i...j] is palindrome if the two ends are equal and the inner substring is palindrome
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
    
    count = 0  # To count the number of valid substrings selected
    i = 0
    # Iterate through the string with pointer i; only consider positions where a substring of length k can start
    while i <= n - k:
        found = False
        # Try to find the smallest ending index j starting from i such that s[i...j] is a valid palindrome substring of length >= k
        for j in range(i + k - 1, n):
            if dp[i][j]:
                count += 1  # Found a valid palindrome substring
                i = j + 1  # Move pointer to j+1 to ensure non-overlapping condition
                found = True
                break
        # If no valid substring was found starting at i, move to the next character
        if not found:
            i += 1
    return count

# Example usage
s = "abaccdbbd"
k = 3
print(max_palindrome_substrings(s, k))  # Expected output: 2
← Back to All Questions