You are given a string text. You should split it to k substrings (subtext1, subtext2, ..., subtextk) such that:
subtexti is a non-empty string.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 <= 1000text consists only of lowercase English characters.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.
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.
Python
C++
Java
JavaScript
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.
Python
C++
Java
JavaScript
We can start from both ends of the string, looking for the shortest, identical, and non-overlapping prefixes and suffixes:
1;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.
Python
Java
C++
Go
TypeScript
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.
| Approach | Complexity |
|---|---|
| Recursive Approach with Two-Pointer Technique |
|
| Dynamic Programming Approach |
|
| Greedy + Two Pointers | — |
| String Hash | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Greedy Two Pointers | O(n^2) | O(n) | Best practical solution. Clean interview approach using prefix–suffix matching. |
| Dynamic Programming | O(n^3) | O(n^2) | Useful for understanding subproblem structure or when exploring all substring states. |
| Greedy with Rolling Hash | O(n^2) | O(n) | Improves substring comparison speed using hashing when strings are large. |
LeetCode 1147. Longest Chunked Palindrome Decomposition Solution Explained - Java • Algorithms and Data Structures Course • 1,042 views views
Watch 9 more video solutions →Practice Longest Chunked Palindrome Decomposition with our built-in code editor and test cases.
Practice on FleetCode