Problem statement

Split text into k non-empty pieces subtext1, subtext2, …, subtextk whose concatenation, in order, is text, such that the pieces read the same from both ends: subtext_i == subtext_(k - i + 1) for every 1 <= i <= k.

Each piece is compared as a whole string — the letters inside a piece are not reversed. Return the largest possible k.

Example 1

Input: text = "kaicodekai"
Output: 3
Explanation: `(kai)(code)(kai)` — the middle piece `code` cannot be split further.

Example 2

Input: text = "merchant"
Output: 1
Explanation: No proper prefix equals the suffix of the same length, so the whole string is one piece.

Example 3

Input: text = "aaa"
Output: 3
Explanation: `(a)(a)(a)`.

Constraints

• 1 <= text.length <= 1000
• text consists only of lowercase English letters

Hints for Longest Chunked Palindrome Decomposition

1. Hint 1

   Look at the outermost pair of pieces: the first piece must equal the last piece.

2. Hint 2

   Take the shortest prefix that equals the suffix of the same length — cutting it off early never hurts, so a greedy choice works.

3. Hint 3

   Repeat on what remains in the middle; if no prefix matches a suffix there, the remaining middle is one last piece.

How to solve Longest Chunked Palindrome Decomposition

Peel the shortest matching prefix/suffix pair off both ends, count 2, and repeat; whatever cannot be peeled is a single middle piece.

Approach

1. Keep start = 0 (the left edge of the unmatched middle) and count = 0.
2. For i from 0 to n - 1, let len = i - start + 1 and compare text[start .. i] with the length-len block ending at n - 1 - start, i.e. text[n - 1 - i .. n - 1 - start].
3. On a match, add 1 and set start = i + 1. Scanning over the whole string counts each outer pair twice (once from each side) and the middle once.
4. Return the count.

Why it works

Exchange argument: if the shortest matching prefix P (length p) is shorter than the first piece Q of an optimal decomposition, then P is both a prefix and a suffix of Q. Replacing the outer pair Q … Q by P, Q', P around a middle gives at least as many pieces when |Q| >= 2p, and when p < |Q| < 2p the overlap makes Q periodic so splitting still works; hence taking P is safe. Recursing on the middle finishes the induction.

Complexity

• Time — O(n^2) with direct comparisons (O(n) with rolling hashes)
• Space — O(1)

Pitfalls

• Pieces are compared as whole strings, not mirrored character by character: "abab" splits as (ab)(ab).
• When the two scans meet in the middle with no match, that middle still counts as one piece.
• Taking the longest matching prefix instead of the shortest loses pieces ("aaa" would give 1).

Reference solution

Python

def longestDecomposition(text: str) -> int:
    n = len(text)
    count = 0
    start = 0
    for i in range(n):
        length = i - start + 1
        if text[start:i + 1] == text[n - 1 - i:n - 1 - i + length]:
            count += 1
            start = i + 1
    return count

Java

public static int longestDecomposition(String text) {
    int n = text.length(), count = 0, start = 0;
    for (int i = 0; i < n; i++) {
        int len = i - start + 1;
        if (text.regionMatches(start, text, n - 1 - i, len)) {
            count++;
            start = i + 1;
        }
    }
    return count;
}

C++

int longestDecomposition(string text) {
    int n = text.size(), count = 0, start = 0;
    for (int i = 0; i < n; i++) {
        int len = i - start + 1;
        if (text.compare(start, len, text, n - 1 - i, len) == 0) {
            count++;
            start = i + 1;
        }
    }
    return count;
}

JavaScript

var longestDecomposition = function(text) {
    var n = text.length, count = 0, start = 0;
    for (var i = 0; i < n; i++) {
        var len = i - start + 1;
        if (text.substr(start, len) === text.substr(n - 1 - i, len)) {
            count++;
            start = i + 1;
        }
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Minimum Changes to Make K Semi-palindromes Hard
• Closest Subsequence Sum Hard
• Maximum Score of a Good Subarray Hard
• Kth Smallest Product of Two Sorted Arrays Hard
• Subsequence With the Minimum Score Hard
• Last Substring in Lexicographical Order Hard