Code Implementation

class Solution:
    def longestDecomposition(self, text: str) -> int:
        n = len(text)
        left, right = 0, n - 1
        ans = 0
        l_chunk, r_chunk = '', ''
        while left <= right:
            l_chunk += text[left]
            r_chunk = text[right] + r_chunk
            if l_chunk == r_chunk:
                ans += 1
                l_chunk = ''
                r_chunk = ''
            left += 1
            right -= 1
        return ans
      

class Solution {
public:
    int longestDecomposition(string text) {
        int n = text.size();
        int left = 0, right = n - 1;
        int ans = 0;
        string l_chunk = "", r_chunk = "";
        while (left <= right) {
            l_chunk += text[left];
            r_chunk = text[right] + r_chunk;
            if (l_chunk == r_chunk) {
                ans++;
                l_chunk = "";
                r_chunk = "";
            }
            left++;
            right--;
        }
        return ans;
    }
};
      

class Solution {
    public int longestDecomposition(String text) {
        int n = text.length();
        int left = 0, right = n - 1;
        int ans = 0;
        StringBuilder l_chunk = new StringBuilder();
        StringBuilder r_chunk = new StringBuilder();
        while (left <= right) {
            l_chunk.append(text.charAt(left));
            r_chunk.insert(0, text.charAt(right));
            if (l_chunk.toString().equals(r_chunk.toString())) {
                ans++;
                l_chunk.setLength(0);
                r_chunk.setLength(0);
            }
            left++;
            right--;
        }
        return ans;
    }
}
      

var longestDecomposition = function(text) {
    let n = text.length;
    let left = 0, right = n - 1;
    let ans = 0;
    let l_chunk = "", r_chunk = "";
    while (left <= right) {
        l_chunk += text[left];
        r_chunk = text[right] + r_chunk;
        if (l_chunk === r_chunk) {
            ans++;
            l_chunk = "";
            r_chunk = "";
        }
        left++;
        right--;
    }
    return ans;
};
      

Problem Description

Given a string text, your task is to split it into the maximum number of non-empty substrings (called "chunks") so that reading the chunks from left to right is the same as reading them from right to left. In other words, the sequence of chunks forms a palindrome.

Each chunk must be a contiguous substring of text. The concatenation of all chunks in order must give back the original string. Chunks can be of any length, but you must maximize the number of chunks.

For example, for text = "ghiabcdefhelloadamhelloabcdefghi", one valid decomposition is ["ghi","abcdef","hello","adam","hello","abcdef","ghi"], which has 7 chunks and forms a palindrome.

Constraints:

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

Thought Process

The core idea is to split the string into as many palindromic "chunks" as possible. At each step, we want to find the smallest matching prefix and suffix, remove them, and repeat the process on the remaining substring. This is similar to "peeling off" matching layers from the outside in.

A brute-force approach might try every possible split, but that would be too slow. Instead, we look for an efficient way to compare prefixes and suffixes as we move inward from both ends of the string.

We can use two pointers: one starting from the left, one from the right. We build up substrings from both ends and compare them. Whenever they match, we've found a chunk, and we reset our substrings and continue inward.

Solution Approach

• Initialize pointers and counters: Set two pointers, left at the start and right at the end of the string. Also, initialize two empty strings (or string builders) to accumulate characters from each end.
• Iterate towards the center: In a loop, add the current character at left to the left chunk, and the character at right to the right chunk (prepend for the right chunk so it grows in the correct order).
• Check for matching chunks: After each addition, compare the left and right chunks. If they are equal, it means we've found a palindromic chunk pair. Increment the chunk count, and reset both chunk strings.
• Move pointers inward: Increment left and decrement right to continue checking the next characters.
• Finish when pointers cross: The process stops when left passes right. Any unmatched middle chunk (when the string length is odd) is counted as a single chunk.
• Return the result: The total number of chunks found is the answer.

This approach ensures that we always maximize the number of chunks, because we always match the smallest possible non-empty prefix and suffix at each step.

Example Walkthrough

Let's walk through the input text = "ghiabcdefhelloadamhelloabcdefghi":

1. First iteration:
   • Left chunk: "g", Right chunk: "i" (not equal)
   • Left chunk: "gh", Right chunk: "hi" (not equal)
   • Left chunk: "ghi", Right chunk: "ghi" (equal!)
   • We found a chunk. Reset both chunks, move pointers inward.
2. Next iterations:
   • Build up "a", "ab", ..., "abcdef" on both sides. When both chunks reach "abcdef", they match. Another chunk found.
   • Repeat for "hello" on both sides. Another chunk.
   • Now left and right pointers are at the substring "adam" in the middle. Since pointers meet, this is a chunk by itself.
3. Result:
   • Total chunks: ["ghi", "abcdef", "hello", "adam", "hello", "abcdef", "ghi"] = 7

At each step, we matched the smallest corresponding prefix and suffix, maximizing the number of chunks.

Time and Space Complexity

• Brute-force approach: Trying all possible splits would be exponential in time, as the number of ways to split grows rapidly with string length.
• Optimized approach (current solution):
  • Time complexity: O(N²), where N is the length of text. In the worst case, comparing chunks can take O(N) time for each of up to N/2 positions.
  • Space complexity: O(N), for the temporary chunk strings or builders.
• For most practical cases, this approach is efficient and works well within the problem's constraints.

Summary

The Longest Chunked Palindrome Decomposition problem asks us to split a string into the largest number of palindromic "chunks" by matching prefixes and suffixes. By using a two-pointer approach and comparing growing substrings from both ends, we efficiently find the maximal decomposition. The key insight is always to match the smallest possible chunks from the outside in, ensuring the solution is optimal and elegant.