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

Longest Chunked Palindrome Decomposition

Number: 1251

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given a string named text, the task is to split it into k non-empty substrings such that the concatenation of these substrings forms the original text and the i-th substring from the beginning is equal to the i-th substring from the end. In other words, for every valid i, subtext_i equals subtext_(k-i+1). The goal is to maximize the number of chunks k.

Key Insights

  • Use a greedy two-pointers approach by comparing potential substring chunks from the beginning and the end of the text.
  • Start with pointers at the leftmost and rightmost ends of the string and try to find the smallest matching pair of substrings.
  • Once a matching pair is found, move the pointers inward and increment the count by 2 (or by 1 if there is a middle unmatched chunk).
  • Continue this process until the pointers meet or cross.
  • The approach guarantees the maximum number of chunks because it always takes the smallest valid matching substring.

Space and Time Complexity

Time Complexity: O(n^2) in the worst case, due to comparing substrings until a match is found at each step. Space Complexity: O(n), if including the space for output or additional substring creation, though the extra space used in the algorithm itself is constant.

Solution

The algorithm uses two pointers (left and right) that move inward from the two ends of the string. At each step, we try every possible length for a candidate substring from the left end and check if it matches the corresponding substring at the right end. When a match is found, it means we have located a pair of palindromic chunks. The left pointer is advanced by the length of the matching substring and the right pointer is moved backward accordingly. This greedy approach ensures that we split the string into the maximum possible number of valid chunks. Special care is taken to handle the middle part when the two pointers meet exactly.

Code Solutions

# Python solution for Longest Chunked Palindrome Decomposition

def longestDecomposition(text):
    # Initialize two pointers, left marking the beginning and right marking the end
    left, right = 0, len(text)
    count = 0
    # Process until all parts of the string are checked
    while left < right:
        # variable to store the length of current chunk
        i = 1
        # Search for the smallest valid matching substring pair
        while left + i <= right:
            # Define the candidate substring from the left side
            left_chunk = text[left:left+i]
            # Define the candidate substring from the right side (reverse order)
            right_chunk = text[right-i:right]
            # If the chunks match, update the pointers and increase the count
            if left_chunk == right_chunk:
                count += 1 if left + i == right - i else 2
                left += i
                right -= i
                break
            i += 1
    return count

# Example usage:
# result = longestDecomposition("ghiabcdefhelloadamhelloabcdefghi")
# print(result)  # Expected output: 7
← Back to All Questions