↓Skip to main content
  1. LeetCode/

LeetCode 1147: Longest Chunked Palindrome Decomposition

·2 mins· ·
LeetCode Hard Dynamic-Programming Greedy Two-Pointers Rolling-Hash String
Wei Yi Chung
Author
Wei Yi Chung
Working at the contributing of open source, distributed systems, and data engineering.
Table of Contents

Meta Data
#

Difficulty: hard First Attempt: 2026-07-01

  • Submissions: Accepted ×2 (written on 2026-07-01 and 08-24)

Approach
#

Greedy: cut as soon as a prefix equals the matching suffix.

Cutting early is best: if the shortest equal prefix/suffix is A and a longer one B is taken as a chunk, B starts and ends with A, so it splits further into A + middle + A, giving more chunks.

Two pointers move inward, accumulating left_str on the left and prepending to right_str on the right; when they match, add 2 chunks and start over. At the end:

  • if the pointers meet on one character (the center of an odd length), or
  • there is an unmatched string left,

that middle part is one more chunk.

My Solution
#

class Solution:
    def longestDecomposition(self, text: str) -> int:
        left, right = 0, len(text) - 1
        left_str = right_str = ""
        chunks = 0
        while left < right:
            left_str += text[left]
            right_str = text[right] + right_str
            if left_str == right_str:              # cut as soon as possible
                chunks += 2
                left_str = right_str = ""
            left += 1
            right -= 1
        if left == right or left_str:              # the leftover middle is one chunk
            chunks += 1
        return chunks

Complexity
#

Time O(n^2) (each string comparison is up to O(n)) with n <= 1000; rolling hashes make it O(n). Space O(n).

Mistakes to Avoid
#

  • Count the leftover middle as one chunk.
  • Prepend on the right (text[right] + right_str) so the order matches the original string.

Interview Explanation
#

Greedily I build strings inward from both ends and cut a pair as soon as they match, since a longer matching prefix/suffix could always be split into shorter ones for more chunks. If a middle part remains, it is one chunk. Time O(n^2), or O(n) with rolling hashes.

Related

LeetCode 1537: Get the Maximum Score
·3 mins
LeetCode Hard Dynamic-Programming Two-Pointers Greedy Array
LeetCode 1537 note: two sorted arrays can switch only at shared values; merge with two pointers, keep a running sum per path, and at a shared value set both to the larger sum plus that value
LeetCode 3952: Maximum Total Value of Covered Indices
·2 mins
LeetCode Medium Dynamic-Programming State-Machine Greedy String
LeetCode 3952 note: each token moves left at most once, so the state is whether this index’s token moved left; moving only helps if the index to the left was not already covered
LeetCode 2697: Lexicographically Smallest Palindrome
·2 mins
LeetCode Easy Two-Pointers String Greedy
LeetCode 2697 note: converging pointers, setting both ends to the smaller character whenever they differ
LeetCode 1745: Palindrome Partitioning IV
·2 mins
LeetCode Hard Dynamic-Programming Interval-Dp String
LeetCode 1745 note: build is_pal[i][j] with interval DP, then try both cut points; three palindromic parts means true, O(n^2)
LeetCode 1793: Maximum Score of a Good Subarray
·3 mins
LeetCode Hard Two-Pointers Greedy Binary-Search Array Monotonic-Stack
LeetCode 1793 note: expand from k toward the larger neighbor each step so the minimum stays as large as possible for each length; at a boundary, only the other side can grow
LeetCode 1616: Split Two Strings to Make Palindrome
·3 mins
LeetCode Medium Two-Pointers String Greedy
LeetCode 1616 note: greedily match a’s prefix against b’s suffix from the outside in; the leftover middle must be a palindrome entirely within a or b, and both directions need checking