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.The key idea in Longest Chunked Palindrome Decomposition is to split the string into the maximum number of symmetric chunks such that the sequence of chunks forms a palindrome. A common strategy is a greedy two‑pointer approach: compare the growing prefix from the left with a growing suffix from the right. When the two substrings match, they form a valid pair of chunks, and the search continues inward.
A straightforward implementation compares substrings directly, but this can be optimized using a rolling hash or hash function to efficiently check equality while expanding both sides. This reduces repeated substring comparisons and improves performance for large inputs.
Some solutions also discuss dynamic programming concepts, but the greedy strategy works because choosing the smallest matching prefix and suffix always leads to the maximum chunk count. The main challenge is efficiently verifying substring equality while moving the pointers.
Typical implementations run in O(n) time with hashing, while simpler comparisons may degrade toward O(n²) in the worst case.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy Two Pointers (Direct String Comparison) | O(n^2) worst case | O(1) |
| Greedy with Rolling Hash | O(n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Using a rolling hash, we can quickly check whether two strings are equal.
Use that as the basis of a dp.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The greedy method works because selecting the smallest matching prefix and suffix ensures the maximum number of chunks. Any larger matching segment would reduce the total chunk count, making the greedy choice optimal.
Yes, variations of this problem appear in high-level coding interviews because it tests string manipulation, greedy reasoning, and hashing techniques. It is considered challenging and suitable for advanced interview rounds.
Strings combined with rolling hash structures are commonly used for efficient comparisons. Hash values allow quick equality checks between prefix and suffix segments without repeatedly creating substrings.
The optimal approach uses a greedy strategy with two pointers that build matching prefixes and suffixes. When combined with rolling hash, substring comparisons become efficient, leading to near O(n) performance.