Longest Chunked Palindrome Decomposition: Greedy Matching

May 27, 20266 min read

leetcodeproblemhardstringsgreedy

LeetCode 1147, Longest Chunked Palindrome Decomposition, asks you to split a string text into k substrings text = a1 + a2 + ... + ak such that ai = a(k+1-i) for all valid i. Your goal is to maximize k. In other words, you are decomposing the string into the largest number of chunks where the first chunk equals the last, the second equals the second-to-last, and so on, like a palindrome but at the chunk level.

"ghiabcdefhelloadamhelloabcdefghi" splits into 7 chunks. Matching pairs share the same color. The center chunk "adam" stands alone.

Why this problem matters

Chunked palindrome decomposition tests a combination of string matching and greedy reasoning. The problem looks like it might require dynamic programming or some heavy string algorithm, but the optimal approach is surprisingly direct. You greedily peel matching chunks from both ends, always taking the shortest match. This "greedy from both ends" pattern is a useful mental model that transfers to other string decomposition and partitioning problems.

The problem also exercises your ability to handle two-pointer logic on strings where the pointers track variable-length windows rather than single elements. That skill shows up in problems involving rolling hashes, substring matching, and text compression.

The key insight

The greedy choice is: always match the shortest possible chunk from the left end with the right end. If you find a match at length 1, take it. Do not wait to see if a longer match exists.

Why does this work? If you match a longer chunk, you are combining what could have been multiple shorter matches into one pair. Since each matched pair contributes 2 to k (or 1 if it is the center), taking shorter matches always produces an equal or larger k. You never lose by being greedy with the shortest match.

Think of it this way. Suppose the left prefix of length 3 matches the right suffix of length 3, and so does the left prefix of length 1 with the right suffix of length 1. If you take the length-3 match, you get +2 to k for that pair. If you take the length-1 match, you get +2 for that pair and still have the remaining characters to potentially match further, giving you even more chunks. Shorter is always at least as good.

The solution

def longestDecomposition(text):
    n = len(text)
    k = 0
    left = 0
    right = n - 1

    while left < right:
        length = 1
        found = False
        while left + length - 1 < right - length + 1:
            if text[left:left + length] == text[right - length + 1:right + 1]:
                k += 2
                left += length
                right -= length
                found = True
                break
            length += 1
        if not found:
            k += 1
            break

    if left == right:
        k += 1
    if left > right and left == right + 1:
        pass

    return k

The algorithm works with two pointers, left starting at the beginning and right starting at the end. At each step, we try increasing chunk lengths starting from 1. We compare text[left:left+length] with text[right-length+1:right+1]. The moment we find a match, we record two chunks (one from each end), advance left forward by length, and pull right back by length. We repeat until the pointers meet or cross.

If the pointers meet exactly (left == right), there is a single center character left, which counts as one more chunk. If the pointers cross without finding a match in the final iteration, the remaining middle section becomes one center chunk.

The greedy choice of always taking the shortest matching chunk is provably optimal. You never need to backtrack or try longer matches. This keeps the implementation simple and avoids the need for dynamic programming.

Practice greedy patterns with spaced repetition

Visual walkthrough

Step 1: Initialize two pointers at opposite ends

L starts at index 0 and R starts at index 8. We will greedily try to match the shortest prefix from L with the shortest suffix ending at R.

Step 2: Try matching chunks of increasing length

Compare text[0..0]="a" with text[8..8]="c". No match. Compare text[0..1]="ab" with text[7..8]="bc". No match. Compare text[0..2]="abc" with text[6..8]="abc". Match found!

Step 3: First pair matched. k = 2. Advance pointers inward.

We matched "abc" on both ends. k increases by 2. L moves to index 3 and R moves to index 5. The remaining substring is "abc" (indices 3 through 5).

Step 4: Remaining "abc" cannot be split further.

L=3, R=5. Compare text[3]="a" with text[5]="c". No match. len=2: text[3..4]="ab" vs text[4..5]="bc". No match. len=3 would consume the entire remainder, so we stop and count it as one center chunk. k += 1.

Step 5: Final result. k = 3 chunks.

"abcabcabc" decomposes into "abc" + "abc" + "abc" where a1 = a3 = "abc" and a2 = "abc" is the center. This is the maximum number of chunks.

The walkthrough above uses "abcabcabc". The first character "a" does not match the last character "c", and neither does "ab" match "bc". But "abc" matches "abc" at both ends. After peeling off that pair, the remaining "abc" in the middle cannot be split further, so it becomes the center chunk. The total is k = 3.

For a string like "ghiabcdefhelloadamhelloabcdefghi", the algorithm finds "ghi" matching on both ends first, then "abcdef", then "hello", leaving "adam" as the center. That gives k = 7.

Complexity analysis

Approach	Time	Space
Greedy two-pointer	O(n^2)	O(n)

Time: O(n^2). In the worst case, for each position of the left pointer, we might try all possible lengths before finding a match (or failing). Each string comparison takes O(length) time. The total work across all iterations sums to O(n^2) because the combined length of all attempted comparisons is bounded by the square of the string length.

Space: O(n). The string slicing in Python creates new string objects for comparison. Each slice is at most O(n) in length. You can reduce this to O(1) extra space by comparing characters one at a time instead of slicing, or by using a rolling hash to speed up the comparisons.

A rolling hash approach (like Rabin-Karp) can bring the expected time down to O(n) by avoiding the O(length) string comparison at each step. But the worst case remains O(n^2) due to hash collisions, and interviewers typically accept the greedy O(n^2) solution for this problem.

The building blocks

1. Greedy shortest-match from both ends

The core technique is scanning from both ends of a string and greedily matching the shortest prefix with the shortest suffix. This pattern shows up whenever you want to maximize the number of symmetric segments. The key mental model is: "shorter matches leave more room for additional matches, so always take the shortest."

This is different from problems like longest common prefix where you want the longest match. Here, the optimization direction is reversed because you are maximizing the count of matches, not the length of any single match.

2. Two-pointer with variable-length windows

Unlike classic two-pointer problems where each pointer moves by one element at a time, here the pointers jump by variable amounts depending on the matched chunk length. You need to maintain the invariant that the unprocessed portion of the string is text[left..right], and each match shrinks this window from both sides.

This variable-stride two-pointer pattern also appears in problems involving run-length encoding, text compression, and repeated substring detection.

Drill string pattern building blocks

Edge cases

Single character. "a" returns 1. There is nothing to match, so the entire string is one chunk.

All identical characters. "aaaa" returns 4. Each single character from the left matches the corresponding single character from the right. You get pairs "a"/"a", "a"/"a", giving k = 4.

No decomposition possible. "merchant" returns 1. No prefix of any length matches the corresponding suffix, so the whole string is a single chunk.

Entire string is a pair. "abab" returns 2. "ab" on the left matches "ab" on the right. The pointers cross, and k = 2.

Odd-length center. "abcba" returns 5. "a" matches "a", "b" matches "b", and "c" is the center. k = 5.

Repeated pattern. "aaa" returns 3. First "a" matches last "a" (k = 2), then the middle "a" is the center (k = 3).

From understanding to recall

Reading this solution once gives you the idea. But when you sit down to code it in an interview next month, the details matter. Where exactly do the pointers start? How do you check if the pointers have crossed? What is the condition for stopping the inner loop so you do not accidentally overlap the left and right chunks? When do you add 1 vs 2 to k?

These small details are exactly what spaced repetition is designed for. The first review cements the overall greedy strategy. The second review locks in the pointer movement logic. By the third review, the edge cases (single character, all identical, odd center) are automatic. You stop thinking about the algorithm and start recognizing it.

The building blocks here, greedy shortest-match and variable-stride two pointers, are small enough to drill independently. Once they are solid, assembling them into the full solution becomes a matter of connecting pieces you already know.

Longest Palindromic Substring - Another palindrome problem, but focused on finding a single longest palindromic substring rather than decomposing into chunks
Palindrome Partitioning - Partitions a string into palindromic substrings using backtracking, a different decomposition strategy
Shortest Palindrome - Uses the longest palindromic prefix concept, which shares the "match from both ends" intuition

Greedy string problems reward pattern recognition. The more problems you drill, the faster you spot the "take the shortest match" signal. CodeBricks uses spaced repetition to make sure these patterns stick in long-term memory so you can recall them under interview pressure.

Try CodeBricks free