Longest Chunked Palindrome Decomposition
HardPrompt
You are given a string text. You should split it to k substrings (subtext1, subtext2, ..., subtextk) such that:
subtextiis a non-empty string.- The concatenation of all the substrings is equal to
text(i.e.,subtext1 + subtext2 + ... + subtextk == text). subtexti == subtextk - i + 1for all valid values ofi(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 <= 1000textconsists only of lowercase English characters.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses recursion with memoization to explore all possible valid decompositions and find the one with the maximum number of chunks. A function solve(i, j) is defined to compute the maximum number of chunks for the substring text[i...j]. This method guarantees correctness by exhaustively checking every possibility.
Algorithm
- Define a recursive function
solve(i, j)which computes the answer fortext.substring(i, j + 1). - Use a 2D array
memo[n][n]to store the results ofsolve(i, j)to avoid re-computation. - The base cases for the recursion are:
- If
i > j(empty substring), return 0. - If
i == j(single character), return 1.
- If
- In
solve(i, j), initialize the resultresto 1, representing the case where the entire substringtext[i...j]is a single chunk. - Iterate with a possible chunk length
lenfrom 1 up to(j - i + 1) / 2. - For each
len, check if the prefixtext[i...i+len-1]is equal to the suffixtext[j-len+1...j]. - If they are equal, it means we can form two chunks. The total number of chunks for this split would be
2 + solve(i + len, j - len). - Update
res = max(res, 2 + solve(i + len, j - len)). - Store the final
resinmemo[i][j]and return it. - The final answer is the result of
solve(0, n-1).
Walkthrough
The state dp(i, j) represents the solution for the substring text[i...j]. The function iterates through all possible lengths len for the first chunk, from 1 up to half the length of the current substring. For each len, it checks if the prefix of length len matches the suffix of length len. If they match, it makes a recursive call for the middle part dp(i + len, j - len) and considers 2 + dp(i + len, j - len) as a possible answer. The function takes the maximum over all possible splits, and also considers the case where the entire substring text[i...j] forms a single chunk (value of 1). A 2D array memo[n][n] is used to store the results to prevent recomputing the same subproblem.
class Solution { private int[][] memo; private String text; private int n; public int longestDecomposition(String text) { this.text = text; this.n = text.length(); this.memo = new int[n][n]; return solve(0, n - 1); } private int solve(int i, int j) { if (i > j) { return 0; } if (i == j) { return 1; } if (memo[i][j] != 0) { return memo[i][j]; } // The whole substring text[i..j] is one chunk int res = 1; // Try to find a matching prefix and suffix for (int len = 1; len <= (j - i + 1) / 2; len++) { if (text.substring(i, i + len).equals(text.substring(j - len + 1, j + 1))) { res = Math.max(res, 2 + solve(i + len, j - len)); } } return memo[i][j] = res; }}Complexity
Time
`O(N^4)`. There are `O(N^2)` states `(i, j)`. For each state of length `L`, we iterate `len` from 1 to `L/2`. The substring comparison takes `O(len)`. The work for one state is `sum_{len=1 to L/2} O(len) = O(L^2)`. The total complexity is `sum_{L=1 to N} (N-L+1) * O(L^2) = O(N^4)`.
Space
`O(N^2)` for the memoization table.
Trade-offs
Pros
It's a straightforward translation of the problem definition into a recursive solution, guaranteeing correctness by exploring all possibilities.
Cons
Extremely inefficient due to the high time complexity, making it infeasible for the given constraints (
N <= 1000).
This approach is based on the greedy observation that to maximize the number of chunks k, we should always choose the shortest possible prefix that matches a suffix. This leaves the largest possible middle section to be decomposed further, maximizing the potential for more chunks. This greedy choice is proven to be optimal.
Algorithm
- Initialize
count = 0,left = 0,right = n - 1. - Start a
whileloop that continues as long asleft <= right. - Inside the loop, set a flag
foundMatch = false. - Start an inner
forloop forlenfrom 1 up to(right - left + 1) / 2. - In the inner loop, check if
text.substring(left, left + len)equalstext.substring(right - len + 1, right + 1). - If they match:
- Increment
countby 2. - Update
left += lenandright -= len. - Set
foundMatch = trueandbreakfrom the inner loop.
- Increment
- After the inner loop, if
foundMatchis false, it means no matching pair was found for the current substring.- Increment
countby 1 (for the middle chunk). breakfrom the outerwhileloop.
- Increment
- Return
count.
Walkthrough
We use two pointers, left and right, initialized to the start and end of the string. We iteratively process the substring text[left...right]. In each iteration, we search for the smallest len >= 1 such that the prefix text[left...left+len-1] equals the suffix text[right-len+1...right]. To do this, we loop len from 1 upwards. Once we find such a match, we have found two chunks. We add 2 to our total count, and shrink the problem space by updating left to left + len and right to right - len. We then restart the search on the new, smaller substring. If the loop for len completes without finding any match, it means the remaining substring text[left...right] cannot be split further. It must form a single, middle chunk. We add 1 to the count and terminate.
class Solution { public int longestDecomposition(String text) { int n = text.length(); int count = 0; int left = 0; int right = n - 1; while (left <= right) { if (left == right) { count++; break; } boolean foundMatch = false; // Check for chunks of length `len` for (int len = 1; len <= (right - left + 1) / 2; len++) { if (text.substring(left, left + len).equals(text.substring(right - len + 1, right + 1))) { count += 2; left += len; right -= len; foundMatch = true; break; } } if (!foundMatch) { // The remaining middle part is one chunk count++; break; } } return count; }}Complexity
Time
`O(N^2)`. In the worst-case scenario, for a substring of length `M`, we might have to check many lengths `len`. The check for each `len` takes `O(len)`. The total work for one step of the outer loop is `sum_{l=1 to k} l = O(k^2)`, where `k` is the length of the matched chunk. Since `sum(k)` is `O(N)`, the total time is bounded by `O(N^2)`.
Space
`O(N)` in Java due to `substring` creating new strings. This can be optimized to `O(1)` by implementing a manual character-by-character comparison instead of using `substring`.
Trade-offs
Pros
Much more efficient than the DP approach.
Simple to understand and implement.
Sufficiently fast to pass the given constraints.
Cons
Not the most optimal solution. The nested loops with string comparisons lead to a quadratic time complexity.
This is an optimization of the greedy approach. The bottleneck in the previous approach is the repeated substring comparisons, which take O(len) time. We can use the Rabin-Karp string hashing algorithm to perform these comparisons in O(1) time on average, leading to a significant speedup.
Algorithm
- Implement a string hashing utility that can compute the hash of any substring in
O(1)after anO(N)precomputation. This involves precomputing powers of a basepand prefix hashes. - Create two instances of the hashing utility: one for the original
textand one for its reverse. - The main logic is the same as the iterative greedy approach (
left,rightpointers,count). - In the inner loop over
len, instead of a character-by-character comparison:- Get the hash of
text[left...left+len-1]. - Get the hash of the corresponding suffix (which is a prefix of the reversed string).
- If the hashes are equal, perform a full string comparison as a final check to resolve potential collisions (though this is often skipped in practice if using double hashing).
- If the strings are equal, update
count,left,right, and break the inner loop.
- Get the hash of
Walkthrough
The core idea is to precompute polynomial rolling hashes for all prefixes of the string. This allows us to find the hash of any substring in O(1) time. To compare a prefix text[left...left+len-1] with a suffix text[right-len+1...right], we compute their hashes. A common technique is to also precompute hashes for the reversed string, as a suffix of the original string corresponds to a prefix of the reversed string, making comparisons straightforward. The greedy logic remains the same: find the shortest matching prefix-suffix pair. With hashing, this check becomes much faster, reducing the overall complexity from quadratic to linear.
class Solution { // Using two long values for double hashing to reduce collisions private static final long P1 = 31, M1 = 1_000_000_007; private static final long P2 = 37, M2 = 1_000_000_009; public int longestDecomposition(String text) { int n = text.length(); long[] p1_powers = new long[n + 1]; long[] p2_powers = new long[n + 1]; long[] h1 = new long[n + 1]; long[] h2 = new long[n + 1]; long[] rh1 = new long[n + 1]; long[] rh2 = new long[n + 1]; p1_powers[0] = 1; p2_powers[0] = 1; for (int i = 0; i < n; i++) { p1_powers[i + 1] = (p1_powers[i] * P1) % M1; p2_powers[i + 1] = (p2_powers[i] * P2) % M2; h1[i + 1] = (h1[i] * P1 + text.charAt(i)) % M1; h2[i + 1] = (h2[i] * P2 + text.charAt(i)) % M2; rh1[i + 1] = (rh1[i] * P1 + text.charAt(n - 1 - i)) % M1; rh2[i + 1] = (rh2[i] * P2 + text.charAt(n - 1 - i)) % M2; } int count = 0; int left = 0; int right = n - 1; while (left <= right) { if (left == right) { count++; break; } boolean foundMatch = false; for (int len = 1; len <= (right - left + 1) / 2; len++) { long prefix_h1 = (h1[left + len] - (h1[left] * p1_powers[len]) % M1 + M1) % M1; long prefix_h2 = (h2[left + len] - (h2[left] * p2_powers[len]) % M2 + M2) % M2; int rev_left = n - 1 - right; long suffix_h1 = (rh1[rev_left + len] - (rh1[rev_left] * p1_powers[len]) % M1 + M1) % M1; long suffix_h2 = (rh2[rev_left + len] - (rh2[rev_left] * p2_powers[len]) % M2 + M2) % M2; if (prefix_h1 == suffix_h1 && prefix_h2 == suffix_h2) { count += 2; left += len; right -= len; foundMatch = true; break; } } if (!foundMatch) { count++; break; } } return count; }}Complexity
Time
`O(N)`. The precomputation of hashes and powers takes `O(N)`. The main `while` loop with the inner `for` loop also runs in `O(N)` time. The `left` pointer advances in steps of `k` (the matched length). The work to find each `k` is `O(k)` because of the `O(1)` hash comparisons. Since the sum of all `k` values is `O(N)`, the total time for the main loop is `O(N)`.
Space
`O(N)` to store the precomputed hashes and powers.
Trade-offs
Pros
The most efficient solution with linear time complexity.
Cons
More complex to implement due to the string hashing logic.
Requires careful handling of modular arithmetic and potential hash collisions.
Solutions
Solution
class Solution {public int longestDecomposition(String text) { int n = text.length(); if (n < 2) { return n; } for (int i = 1; i <= n >> 1; ++i) { if (text.substring(0, i).equals(text.substring(n - i))) { return 2 + longestDecomposition(text.substring(i, n - i)); } } return 1; }}class Solution {public: int longestDecomposition(string text) { int n = text.size(); if (n < 2) return n; for (int i = 1; i <= n >> 1; ++i) { if (text.substr(0, i) == text.substr(n - i)) { return 2 + longestDecomposition(text.substr(i, n - i - i)); } } return 1; }};class Solution: def longestDecomposition(self, text: str) -> int: n = len(text) if n < 2: return n for i in range(n // 2 + 1): if text[: i] == text[- i:]: return 2 + self . longestDecomposition(text[i: - i]) return 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.