Manacher Radii

Problem

Return the Manacher radii for odd-length palindromes: d1[i] is the number of characters in the longest odd palindrome centered at index i.

Use the linear Manacher algorithm that reuses the mirrored radius inside the current rightmost palindrome. Return an empty list for an empty string.

Hint

A radius of k means the palindrome spans from i - k + 1 through i + k - 1.

case 1

in: ["babad"]

expected: [1,2,2,1,1]

case 2

in: ["aaaa"]

expected: [1,2,2,1]

case 3

in: ["abc"]

expected: [1,1,1]

case 4

in: ["a"]

expected: [1]

case 5

in: [""]

expected: []

Starter codePython

def manacher_radii(s):
    # Your code here
    pass

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