1147. Longest Chunked Palindrome Decomposition

Description

Given a string text, we need to split it into k substrings such that:

1. Each substring is non-empty.
2. The concatenation of all substrings equals text.
3. subtext<sub>i</sub> == subtext<sub>k - i + 1</sub> for all valid i.

The goal is to find the maximum possible value of k.

Solution 1: Greedy + Two Pointers

This solution employs a greedy approach using two pointers. We iterate from both ends of the string, searching for the shortest identical non-overlapping prefixes and suffixes.

Algorithm:

1. Initialize two pointers, i and j, to the beginning and end of the string, respectively.
2. Iterate while i ≤ j:
   • Try to find matching prefixes and suffixes of increasing length (k).
   • If a match is found (text[i:i+k] == text[j-k+1:j+1]):
     • Increment ans by 2 (since we found a pair of matching substrings).
     • Move i and j to skip the matched substrings.
     • Continue to the next iteration.
   • If no match is found for any k:
     • Increment ans by 1 (the remaining part is a single palindrome chunk).
     • Break the loop.
3. Return ans.

Time Complexity: O(n^2) in the worst case, where n is the length of the string. This happens when we need to check all possible prefix/suffix lengths for each position.

Space Complexity: O(1). We only use a constant amount of extra space.

Code (Python):

class Solution:
    def longestDecomposition(self, text: str) -> int:
        ans = 0
        i, j = 0, len(text) - 1
        while i <= j:
            k = 1
            ok = False
            while i + k - 1 < j - k + 1:
                if text[i : i + k] == text[j - k + 1 : j + 1]:
                    ans += 2
                    i += k
                    j -= k
                    ok = True
                    break
                k += 1
            if not ok:
                ans += 1
                break
        return ans

Code (Java):

class Solution {
    public int longestDecomposition(String text) {
        int ans = 0;
        for (int i = 0, j = text.length() - 1; i <= j;) {
            boolean ok = false;
            for (int k = 1; i + k - 1 < j - k + 1; ++k) {
                if (check(text, i, j - k + 1, k)) {
                    ans += 2;
                    i += k;
                    j -= k;
                    ok = true;
                    break;
                }
            }
            if (!ok) {
                ++ans;
                break;
            }
        }
        return ans;
    }
 
    private boolean check(String s, int i, int j, int k) {
        while (k-- > 0) {
            if (s.charAt(i++) != s.charAt(j++)) {
                return false;
            }
        }
        return true;
    }
}

Similar code can be written in other languages like C++, Go, and JavaScript following the same logic.

Solution 2: String Hash

This solution optimizes the string comparison using a rolling hash function. Instead of directly comparing substrings, we compute their hash values and compare the hashes for quicker equality checks.

Algorithm:

1. Precompute a rolling hash for the input string.
2. Use a similar two-pointer approach as in Solution 1, but compare hash values instead of substrings directly.
3. Handle potential hash collisions gracefully.

Time Complexity: O(n) on average, assuming minimal hash collisions. Hash computation takes linear time.

Space Complexity: O(n) to store the hash values.

Code (Python):

class Solution:
    def longestDecomposition(self, text: str) -> int:
        def get(l, r):
            return (h[r] - h[l - 1] * p[r - l + 1]) % mod
 
        n = len(text)
        base = 131
        mod = int(1e9) + 7
        h = [0] * (n + 10)
        p = [1] * (n + 10)
        for i, c in enumerate(text):
            t = ord(c) - ord('a') + 1
            h[i + 1] = (h[i] * base) % mod + t
            p[i + 1] = (p[i] * base) % mod
 
        ans = 0
        i, j = 0, n - 1
        while i <= j:
            k = 1
            ok = False
            while i + k - 1 < j - k + 1:
                if get(i + 1, i + k) == get(j - k + 2, j + 1):
                    ans += 2
                    i += k
                    j -= k
                    ok = True
                    break
                k += 1
            if not ok:
                ans += 1
                break
        return ans

Again, similar code can be adapted for other languages. The core idea remains consistent: use a rolling hash for efficient string comparisons. Note that the choice of hash function and its parameters (base, modulo) is crucial for minimizing collisions. This approach trades off a bit of space complexity for a significant improvement in time complexity, making it more suitable for larger input strings.