Scale Engineer

Longest Chunked Palindrome Decomposition

Hard
#1080Time: `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.
Patterns
Two PointersDynamic ProgrammingGreedyRolling HashHash Function
Data structures
String

Prompt

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

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 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).

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).

Solutions

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

Video 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.

← Previous

Previous problem

Next →

Next problem