Longest Chunked Palindrome Decomposition

hard greedy two pointers strings

Problem

You are given a string text. Split it into a sequence of non-empty substrings (chunks) so that concatenating them in order reproduces text, and the sequence of chunks reads the same forwards and backwards (chunk i equals chunk k−1−i). Return the largest possible number of chunks k.

Inputtext = "ghiabcdefhelloadamhelloabcdefghi"

Output7

It splits as (ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi) — 7 mirror-matched chunks.

text (lowercase letters)

def longest_decomposition(text):
    count = 0
    i, j = 0, len(text) - 1
    lo, hi = 0, j
    while i < j:
        if text[lo:i + 1] == text[j:hi + 1]:
            count += 2
            i += 1
            lo = i
            j -= 1
            hi = j
        else:
            i += 1
            j -= 1
    if lo <= hi:
        count += 1
    return count

function longestDecomposition(text) {
  let count = 0;
  let i = 0, j = text.length - 1;
  let lo = 0, hi = j;
  while (i < j) {
    if (text.slice(lo, i + 1) === text.slice(j, hi + 1)) {
      count += 2;
      i += 1; lo = i;
      j -= 1; hi = j;
    } else {
      i += 1; j -= 1;
    }
  }
  if (lo <= hi) count += 1;
  return count;
}

class Solution {
    public int longestDecomposition(String text) {
        int count = 0;
        int i = 0, j = text.length() - 1;
        int lo = 0, hi = j;
        while (i < j) {
            if (text.substring(lo, i + 1).equals(text.substring(j, hi + 1))) {
                count += 2;
                i += 1; lo = i;
                j -= 1; hi = j;
            } else {
                i += 1; j -= 1;
            }
        }
        if (lo <= hi) count += 1;
        return count;
    }
}

int longestDecomposition(string text) {
    int count = 0;
    int i = 0, j = (int)text.size() - 1;
    int lo = 0, hi = j;
    while (i < j) {
        if (text.substr(lo, i - lo + 1) == text.substr(j, hi - j + 1)) {
            count += 2;
            i += 1; lo = i;
            j -= 1; hi = j;
        } else {
            i += 1; j -= 1;
        }
    }
    if (lo <= hi) count += 1;
    return count;
}

Explanation

We want the most chunks possible, where the chunk sequence mirrors itself (first equals last, second equals second-to-last, and so on). The key insight is to be greedy: as soon as a small prefix matches a small suffix, cut both off and keep going inward.

Why is grabbing the shortest matching pair right? Because shorter chunks leave more string in the middle, which means more chances to split again. Taking a longer match than necessary could only reduce the final count.

We grow a prefix window [lo..i] from the left and a suffix window [j..hi] from the right at the same time. Whenever the two slices are equal, we count both chunks (count += 2) and reset the windows to start fresh just inside what we removed.

When the pointers finally cross, anything left in the middle that wasn't paired off forms one extra chunk (the palindrome center), so we add 1 if lo <= hi.

Example: text = "volvo". Prefix "v" matches suffix "o"? No. Grow. Prefix "vo" matches suffix "vo"? Yes — take both, count = 2. The middle "l" is left over, add one more, giving 3.

Time: O(n²) Space: O(n)