Problem statement

https://leetcode.com/problems/longest-chunked-palindrome-decomposition/

Solution

The idea is to use rolling hash to check if suffix and prefix are equal and when we found equal prefix and suffix, we can greedily take it. Why? Imagine the case abca...abca: it happen that if we can take bigger suffix, there is always the way to cut it in smaller pieces. So, we follow greedy strategy and each time look for smallest suffix and prefix which are equal. We use rolling hashed for this and we we have equal codes, we can check strings itselfs.

step(x, y) function will work with substring s[x:y+1] (where x+y always equal to n-1): we create empty codes and then try to add element by element and compare codes. If we found equal codes and strings, we add 2 to final answer and return new coordinates. If we did not found equal suffix and prefix, we return (1, 0) as indicator that we have empty string and add 1 to answer.

Then we do x, y = step(x, y) step until x <= y and return answer.

Complexity

Time complexity will be O(n) in average if we do not count collisions. Space complexity is O(n) as well due to recursion stack, which can be made O(1).

Code

class Solution:
    def longestDecomposition(self, s):
        def step(x, y):
            D, i, j = 1, x, y
            code1, code2, d, q = 0, 0, 256, (1<<31) - 1
            while i < j:
                code1 = (code1 * d + ord(s[i]))%q
                code2 = (code2 + ord(s[j])*D)%q
                D, i, j = (D * d)%q, i + 1, j - 1
                if code1 == code2 and s[x:i] == s[j+1:y+1]:
                    self.ans += 2
                    return (i, j)
                
            self.ans += 1
            return (1, 0)
          
        self.ans, x, y = 0, 0, len(s) - 1
        while x <= y: x, y = step(x, y)
        return self.ans

Solution 2

There is also pure dp solution, where dp(i, j) is answer for substring text[i:j+1] Note, that it actually will be called only on O(n) subproblems.

Complexity

Time seems to be O(n^3) but in practice it works quite fast, because string comparison is very very fast in python.

Code

class Solution:
    def longestDecomposition(self, text):
        @lru_cache(None)
        def dp(i, j):
            if i > j: return 0
            if i == j: return 1
            k, tmp = 0, 1
            while i + k < j - k:
                if text[i:i+k+1] == text[j-k:j+1]:
                    tmp = max(tmp, 2 + dp(i+k+1,j-k-1))
                k += 1
            return tmp

        return dp(0, len(text) - 1)