Skip to main content
Talentd

Longest Chunked Palindrome Decomposition - Solution & Explanation

HardTwo PointersStringDynamic ProgrammingGreedy21 min readAsked at: Google
Practice this problem

Problem Statement

You are given a string text. You should split it to k substrings (subtext1, subtext2, ..., subtextk) such that:

  • subtexti is a non-empty string.
  • The concatenation of all the substrings is equal to text (i.e., subtext1 + subtext2 + ... + subtextk == text).
  • subtexti == subtextk - i + 1 for all valid values of i (i.e., 1 <= i <= k).

Return the largest possible value of k.

 

Example 1:

Input: text = "ghiabcdefhelloadamhelloabcdefghi"
Output: 7
Explanation: We can split the string on "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)".

Example 2:

Input: text = "merchant"
Output: 1
Explanation: We can split the string on "(merchant)".

Example 3:

Input: text = "antaprezatepzapreanta"
Output: 11
Explanation: We can split the string on "(a)(nt)(a)(pre)(za)(tep)(za)(pre)(a)(nt)(a)".

 

Constraints:

  • 1 <= text.length <= 1000
  • text consists only of lowercase English characters.

Approach Overview

Problem Overview: You are given a string text. The goal is to split it into the maximum number of non‑empty chunks so that the sequence of chunks forms a palindrome. That means the first chunk equals the last chunk, the second equals the second‑last, and so on.

Approach 1: Recursive Greedy with Two Pointers (O(n^2) time, O(n) space)

This approach uses a greedy observation: the earliest prefix that matches a suffix should form a pair of chunks. Start with two pointers scanning from the beginning and end of the string. Gradually increase the prefix length and check if it equals the corresponding suffix substring. Once a match is found, you lock those two chunks and recursively process the remaining middle substring. In the worst case, substring comparisons take O(n) and happen up to O(n) times, giving O(n^2) time complexity with O(n) recursion depth. This technique relies heavily on string comparison and the idea of symmetric growth from both ends, which makes it a natural fit for Two Pointers and greedy thinking.

Approach 2: Dynamic Programming (O(n^3) time, O(n^2) space)

The dynamic programming formulation considers every substring text[i..j] and computes the maximum chunked decomposition inside it. For each substring, iterate over possible prefix lengths k. If text[i..i+k-1] equals text[j-k+1..j], those form matching chunks and the answer becomes 2 + dp[i+k][j-k]. If no such pair exists, the substring itself forms a single chunk. Since there are O(n^2) substrings and up to O(n) prefix checks per state, the complexity becomes O(n^3) with O(n^2) memory. This formulation clearly demonstrates the overlapping subproblems and transition logic typical in Dynamic Programming.

In practice, substring equality checks can be optimized using hashing. A Rolling Hash allows constant‑time prefix and suffix comparisons, reducing the cost of equality checks and improving practical performance, especially for large strings.

Recommended for interviews: The recursive greedy two‑pointer solution is what most interviewers expect. It shows that you recognize the symmetry in the problem and can shrink the string from both ends while counting chunk pairs. The dynamic programming version demonstrates deeper reasoning about subproblems but is rarely the optimal choice during interviews due to its higher complexity.

Approach 1: Recursive Approach with Two-Pointer Technique

This approach uses recursion along with a two-pointer technique. We start by comparing prefixes and suffixes of the string, reducing the problem as we find mirrored chunks and recursively solving the smaller problem for the middle part. This approach takes advantage of the palindrome property (mirrored chunks) to maximize the number of splits.

In the recursive function helper, we compare the prefixes and suffixes of the substring defined by two pointers left and right. If we find a palindrome chunk, we move inward and recursively solve for the center portion. If no chunk is found, the string itself is a palindrome, contributing 1 to the count.

Code

PythonC++JavaJavaScript

Python

C++

Java

JavaScript

Complexity

  • Time Complexity: O(N^2), due to the recursive nature and substring operations.
  • Space Complexity: O(N), for the recursion stack.
Try this approach in the editor →

Approach 2: Dynamic Programming Approach

In this approach, we use dynamic programming to optimally determine the number of mirrored chunks. We construct a table where each entry signifies the maximum number of chunks that can be made within a certain substring range. Thus, we fill the table by checking all possible matching starting and ending substring pairs.

A table dp is used where each index i holds the maximum number of mirrored chunks for the substring text[0:i]. For each substring that is itself a palindrome, the table is updated with the maximum possible value of chunk count using previously computed results.

Code

PythonC++JavaJavaScript

Python

C++

Java

JavaScript

Complexity

  • Time Complexity: O(N^3), due to the necessity of checking every i-j combination for palindrome property.
  • Space Complexity: O(N), for storing intermediate results.
Try this approach in the editor →

Approach 3: Greedy + Two Pointers

We can start from both ends of the string, looking for the shortest, identical, and non-overlapping prefixes and suffixes:

  • If such prefixes and suffixes cannot be found, then the entire string is treated as a segmented palindrome, and the answer is incremented by 1;
  • If such prefixes and suffixes are found, then this prefix and suffix are treated as a segmented palindrome, and the answer is incremented by 2, then continue to find the prefixes and suffixes of the remaining string.

The proof of the above greedy strategy is as follows:

Suppose there is a prefix A_1 and a suffix A_2 that meet the conditions, and there is a prefix B_1 and a suffix B_4 that meet the conditions. Since A_1 = A_2 and B_1=B_4, then B_3=B_1=B_4=B_2, and C_1 = C_2. Therefore, if we greedily split B_1 and B_4, then the remaining C_1 and C_2, and B_2 and B_3 can also be successfully split. Therefore, we should greedily choose the shortest identical prefix and suffix to split, so that in the remaining string, more segmented palindromes may be split.

The time complexity is O(n^2), and the space complexity is O(n) or O(1). Here, n is the length of the string.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 4: String Hash

String hash is to map a string of any length to a non-negative integer, and its collision probability is almost 0. String hash is used to calculate the hash value of a string and quickly determine whether two strings are equal.

Therefore, based on Solution 1, we can use the method of string hash to compare whether two strings are equal in O(1) time.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Approach with Two-Pointer Technique
  • Time Complexity: O(N^2), due to the recursive nature and substring operations.
  • Space Complexity: O(N), for the recursion stack.
Dynamic Programming Approach
  • Time Complexity: O(N^3), due to the necessity of checking every i-j combination for palindrome property.
  • Space Complexity: O(N), for storing intermediate results.
Greedy + Two Pointers—
String Hash—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive Greedy Two PointersO(n^2)O(n)Best practical solution. Clean interview approach using prefix–suffix matching.
Dynamic ProgrammingO(n^3)O(n^2)Useful for understanding subproblem structure or when exploring all substring states.
Greedy with Rolling HashO(n^2)O(n)Improves substring comparison speed using hashing when strings are large.

Video Solution

LeetCode 1147. Longest Chunked Palindrome Decomposition Solution Explained - Java • Algorithms and Data Structures Course • 1,059 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Longest Chunked Palindrome Decomposition easy or hard?
LeetCode classifies this problem as Hard because recognizing the greedy symmetry is not obvious. Once the insight is clear, the implementation is relatively short, but discovering the chunk‑matching strategy is the main challenge.
Longest Chunked Palindrome Decomposition Python/Java solution
The standard implementation uses recursion with two pointers. You repeatedly compare prefixes and suffixes and recursively process the remaining substring. This approach translates directly to Python, Java, C++, and JavaScript with identical logic and O(n^2) complexity.
How to solve Longest Chunked Palindrome Decomposition in O(n)?
A strict O(n) solution is difficult with direct string comparisons. However, using rolling hash techniques can reduce substring equality checks to constant time, improving practical performance close to linear scanning behavior while still having theoretical O(n^2) worst‑case complexity.
What is the best approach for Longest Chunked Palindrome Decomposition?
The greedy recursive approach using two pointers is considered the best solution. It scans prefixes from the start and matches them with suffixes from the end, forming chunk pairs whenever they match. This approach runs in O(n^2) time due to substring comparisons and uses O(n) recursion space.
Is Longest Chunked Palindrome Decomposition asked at Google/Amazon/Meta?
Variants of this problem appear in interviews at large tech companies because it tests string manipulation, greedy reasoning, and recursion. Similar symmetric decomposition or prefix–suffix matching questions have been reported in Google and Amazon interview preparation resources.
What data structure is used in Longest Chunked Palindrome Decomposition?
The core solution primarily uses string operations and the two‑pointer technique. Some optimized implementations add rolling hash arrays or dynamic programming tables to speed up substring comparisons and store intermediate results.
What is the time complexity of Longest Chunked Palindrome Decomposition?
The common greedy two‑pointer solution runs in O(n^2) time because each prefix comparison may take up to O(n). The dynamic programming approach is slower with O(n^3) time due to checking all substrings and possible chunk sizes. Space complexity ranges from O(n) for recursion to O(n^2) for DP tables.

Ready to solve this problem?

Practice Longest Chunked Palindrome Decomposition with our built-in code editor and test cases.

Practice on FleetCode
Previous

Palindrome Rearrangement Queries