Longest Chunked Palindrome Decomposition

Problem Id: 1147 Difficulty: Hard


Intuition

Solution


class Solution:
    def longestDecomposition(self, text: str) -> int:
        if not text:
            return 0
        self.cache = {}
        if text in self.cache:
            return self.cache[text]

        ans = 1
        for i in range(1, len(text) // 2 + 1):
            if text[:i] == text[-i:]:
                ans = max(ans, self.longestDecomposition(text[i:-i]) + 2)
        if len(text) % 2 == 0 and text[:len(text) // 2] == text[-len(text) // 2:]:
            ans = max(ans, 2)
        self.cache[text] = ans
        return ans