# Longest Chunked Palindrome Decomposition
**Difficulty:** HARD
[External](https://leetcode.com/problems/longest-chunked-palindrome-decomposition)
Canonical: https://scaleengineer.com/dsa/problems/longest-chunked-palindrome-decomposition
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Rolling Hash](https://scaleengineer.com/dsa/patterns/rolling-hash), [Hash Function](https://scaleengineer.com/dsa/patterns/hash-function)
**Data structures:** String
---
## Problem
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.

# Approaches
## Dynamic Programming
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.
**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.
**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`).
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
*   Define a recursive function `solve(i, j)` which computes the answer for `text.substring(i, j + 1)`.
*   Use a 2D array `memo[n][n]` to store the results of `solve(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.
*   In `solve(i, j)`, initialize the result `res` to 1, representing the case where the entire substring `text[i...j]` is a single chunk.
*   Iterate with a possible chunk length `len` from 1 up to `(j - i + 1) / 2`.
*   For each `len`, check if the prefix `text[i...i+len-1]` is equal to the suffix `text[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 `res` in `memo[i][j]` and return it.
*   The final answer is the result of `solve(0, n-1)`.

## Greedy Iterative Approach
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.
**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`.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
*   Initialize `count = 0`, `left = 0`, `right = n - 1`.
*   Start a `while` loop that continues as long as `left <= right`.
*   Inside the loop, set a flag `foundMatch = false`.
*   Start an inner `for` loop for `len` from 1 up to `(right - left + 1) / 2`.
*   In the inner loop, check if `text.substring(left, left + len)` equals `text.substring(right - len + 1, right + 1)`.
*   If they match:
    *   Increment `count` by 2.
    *   Update `left += len` and `right -= len`.
    *   Set `foundMatch = true` and `break` from the inner loop.
*   After the inner loop, if `foundMatch` is false, it means no matching pair was found for the current substring.
    *   Increment `count` by 1 (for the middle chunk).
    *   `break` from the outer `while` loop.
*   Return `count`.

## Greedy Approach with String Hashing
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
*   Implement a string hashing utility that can compute the hash of any substring in `O(1)` after an `O(N)` precomputation. This involves precomputing powers of a base `p` and prefix hashes.
*   Create two instances of the hashing utility: one for the original `text` and one for its reverse.
*   The main logic is the same as the iterative greedy approach (`left`, `right` pointers, `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.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 1

```