BinarySearch 0405 Make Palindrome by Adding a Suffix

Problem statement

/

Solution

Variation of Leetcode 0214. Shortest Palindrome, but reverse string.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, s):
        def prefix(s):
            p = [0] * len(s)
            for i in range(1, len(s)):
                k = p[i - 1]
                while k > 0 and s[k] != s[i]:
                    k = p[k - 1]
                if s[k] == s[i]:
                    k += 1
                p[i] = k
            return p
        
        max_index = prefix(s[::-1] + "!" + s)[-1]
        return len(s) - max_index