Longest chunked palindrome decomposition

Two Pointers String Dynamic Programming Greedy Rolling Hash Hash Function

59.0% acceptance

Feb 25, 2026

709

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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn longest_decomposition(text: String) -> i32 {
    Self::solve(text.as_bytes())
  }

  fn solve(s: &[u8]) -> i32 {
    let n = s.len();
    if n == 0 { return 0; }
    for len in 1..=n/2 {
      if s[..len] == s[n-len..] {
        return 2 + Self::solve(&s[len..n-len]);
      }
    }
    1
  }
}