Watch 10 video solutions for Longest Chunked Palindrome Decomposition, a hard level problem involving Two Pointers, String, Dynamic Programming. This walkthrough by Algorithms and Data Structures Course has 1,042 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |