Minimum letters to be added to make string a palindrome

minimum_characters_to_be_added_to_make_palindrome.py

"""
https://scammingthecodinginterview.com
Week 4: Strings
Problem: 2
"""


class Solution(object):

    def solve(self, s):

        concatenated_s = s + '$' + s[::-1]

        print(concatenated_s)

        lps = self.compute_lps(concatenated_s)

        last_lps = lps[-1]

        ans = len(s) - last_lps

        return ans

    def compute_lps(self, s):

        n = len(s)
        lps = [0 for i in range(0, n)]

        lps[0] = 0
        l = 0

        i = 1
        while i < n:

            if s[i] == s[l]:
                l += 1
                lps[i] = l
                i += 1

            else:

                if l != 0:
                    l = lps[l - 1]
                else:
                    lps[i] = 0
                    i += 1

        return lps


if __name__ == "__main__":

    a = "AACECAAAA"
    ans = Solution().solve(a)
    print(ans)