LeetCode 1147 - Longest Chunked Palindrome Decomposition

The problem asks us to decompose a given string text into the largest possible number of contiguous substrings such that the sequence of substrings forms a palindromic pattern.

leetcodehardtwo-pointersstringdynamic-programminggreedyrolling-hashhash-function

LeetCode Problem 1147

Difficulty: 🔴 Hard
Topics: Two Pointers, String, Dynamic Programming, Greedy, Rolling Hash, Hash Function

Solution

Problem Understanding

The problem asks us to decompose a given string text into the largest possible number of contiguous substrings such that the sequence of substrings forms a palindromic pattern. Specifically, the first substring must equal the last substring, the second substring must equal the second-to-last substring, and so on. The goal is to maximize the number of these chunks, denoted as k.

The input text is a string of length up to 1000 characters, consisting only of lowercase English letters. The output is a single integer representing the maximum number of chunks into which the string can be split while preserving the palindromic chunk property.

The constraints imply that brute-force checking of all possible splits would likely be inefficient. Edge cases include strings that are already palindromic, strings with no repeating patterns, and strings where the maximal decomposition involves many small chunks. The problem guarantees that the string is non-empty, which simplifies handling boundary cases.

Approaches

The brute-force approach would attempt to split the string at every possible prefix and recursively check if the remaining string can also be split into palindromic chunks. While this guarantees correctness, it is highly inefficient because it explores an exponential number of substring combinations, which is infeasible for the upper limit of 1000 characters.

The key insight for an optimal solution is that we do not need to check every possible combination. We can use a two-pointer approach starting from the left and right ends of the string. At each step, we incrementally check if a prefix of the string matches a corresponding suffix. When a match is found, it forms one palindromic chunk, and we recursively or iteratively process the remaining middle portion. This approach works because once a matching pair is identified, it is guaranteed that the optimal decomposition must include it to maximize k. Optionally, a rolling hash can optimize the string comparison, but for n <= 1000, direct substring comparison is sufficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Recursively tries all split combinations; exponential time
Optimal O(n^2) O(1) Two-pointer incremental comparison; substring checks dominate

Algorithm Walkthrough

  1. Initialize two pointers, left starting at the beginning of the string and right at the end. Initialize a counter count to track the number of palindromic chunks.
  2. While left <= right, attempt to find the smallest non-empty prefix starting at left that matches a suffix ending at right.
  3. Use an inner loop to incrementally expand the prefix size. At each step, check if text[left:left+size] == text[right-size+1:right+1].
  4. If a match is found:
  • Increment count by 2 if the prefix and suffix are distinct, or by 1 if left and right point to the same remaining substring (i.e., middle chunk in an odd-length decomposition).
  • Move left past the matched prefix and right before the matched suffix.
  1. Repeat until the pointers cross. Return count.

Why it works: At each iteration, the algorithm greedily identifies the smallest matching prefix-suffix pair. Since any optimal solution must include the outermost matching chunks to maximize the total number of chunks, this approach guarantees the largest possible k. It avoids redundant work by only checking contiguous prefix-suffix pairs.

Python Solution

class Solution:
    def longestDecomposition(self, text: str) -> int:
        n = len(text)
        left, right = 0, n - 1
        count = 0
        
        while left <= right:
            size = 1
            found = False
            while left + size - 1 < right:
                if text[left:left+size] == text[right-size+1:right+1]:
                    count += 2
                    left += size
                    right -= size
                    found = True
                    break
                size += 1
            if not found:
                count += 1
                break
        
        return count

Implementation walkthrough: We initialize two pointers and a chunk counter. The inner loop checks prefixes against corresponding suffixes. When a match is found, we count the two chunks and move the pointers inward. If no match is found before pointers cross, the remaining middle substring is counted as one chunk.

Go Solution

func longestDecomposition(text string) int {
    left, right := 0, len(text)-1
    count := 0
    
    for left <= right {
        size := 1
        found := false
        for left+size-1 < right {
            if text[left:left+size] == text[right-size+1:right+1] {
                count += 2
                left += size
                right -= size
                found = true
                break
            }
            size++
        }
        if !found {
            count++
            break
        }
    }
    
    return count
}

Go-specific notes: Go slices make substring comparison straightforward, similar to Python. The main difference is handling string slicing with [start:end] notation and explicitly managing indices.

Worked Examples

Example 1: "ghiabcdefhelloadamhelloabcdefghi"

Step left right size Match? count
1 0 28 3 Yes 2
2 3 25 6 Yes 4
3 9 19 5 Yes 6
4 14 14 1 Single remaining 7

Example 2: "merchant"

No matching prefix-suffix until pointers cross. count = 1.

Example 3: "antaprezatepzapreanta"

Step left right size Match? count
1 0 19 1 Yes 2
2 1 18 2 Yes 4
3 3 16 1 Yes 6
4 4 15 3 Yes 8
5 7 12 3 Yes 10
6 10 9 Remaining middle 11

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) For each outer iteration, we may scan up to n characters to find matching prefix-suffix pairs
Space O(1) Only pointers and counters are used, no additional data structures

Even though substring comparison is linear in length, the total number of characters compared across all iterations is bounded by O(n^2). For n ≤ 1000, this is acceptable.

Test Cases

# Provided examples
assert Solution().longestDecomposition("ghiabcdefhelloadamhelloabcdefghi") == 7  # standard case
assert Solution().longestDecomposition("merchant") == 1  # no match
assert Solution().longestDecomposition("antaprezatepzapreanta") == 11  # multiple small chunks

# Boundary values
assert Solution().longestDecomposition("a") == 1  # single character
assert Solution().longestDecomposition("aa") == 2  # two identical characters
assert Solution().longestDecomposition("ab") == 1  # two distinct characters

# Stress case
assert Solution().longestDecomposition("abcde"*200) == 1  # long repeated pattern but no prefix-suffix match
Test Why
"ghiabcdefhelloadamhelloabcdefghi" Standard decomposition with multiple chunks
"merchant" No palindromic chunks except whole string
"antaprezatepzapreanta" Odd-length decomposition with many small chunks
"a", "aa", "ab" Boundary cases for short strings
Long repeated pattern Tests efficiency on large input without matching chunks

Edge Cases

Single-character string: For text = "a", the result must be 1. The algorithm correctly handles this because left equals right, and the loop counts the remaining middle chunk.

No matching prefix-suffix: For a string like "abcd", there are no palindromic chunks beyond the whole string. The inner loop fails to find a match, and the remaining string is counted as one chunk.

All identical characters: For text = "aaaa", the algorithm finds matching prefixes and suffixes at every step. It increments count correctly, producing a maximum decomposition of 4 chunks. This ensures the greedy approach works even when multiple valid prefix-suffix choices exist.