Longest Chunked Palindrome Decomposition

Problem

Split the string into the maximum number of chunks so that the first chunk equals the last, the second equals the second last, and so on.

Greedily look for the shortest prefix that matches the equally long suffix; when found, add two chunks and continue with the middle. If no split exists, the whole remainder counts as one chunk.

Hint

Taking the shortest possible matching pair leaves the most room for further chunks.

Test cases

case 1

in: ["ghiabcdefhelloadamhiabcdefgh"]

expected: 7

case 2

in: ["merchant"]

expected: 1

case 3

in: ["antaprezatepzapreanta"]

expected: 11

case 4

in: ["aaa"]

expected: 3

case 5

in: ["aa"]

expected: 2

Starter codePython

def longest_chunked_palindrome(text):
    # Your code here
    pass

5 test cases · run your code against them in the editor