Minimum Appends for Palindrome!

Given a string s we need to tell minimum characters to be appended (insertion at end) to make a string palindrome.

Input : s = "abede"
Output : 2
We can make string palindrome as "abedeba"
by adding ba at the end of the string.

Input : s = "aabb"
Output : 2
We can make string palindrome as"aabbaa"
by adding aa at the end of the string.

Solution

Lets start. Its a simple question. We have to return the minimum number of appends to a string to make a palindrome, that is how many characters should be added at the end to make a palindrome. Now we need to get whether string is palindrome or not starting from the last position.

• Take s = “aworoao”,
  We see “oao” is palindrome starting from index 4 and we only to need to see characters before it. So “awor” comes before the palindrome we found. Just adding those characters to the end would make the string palindrome.
  “aworoaorowa”. length of characters to add will be palindrome’s starting index, that is 4. Because we know all characters after that dont need to be appended as they are already palindrome
• Now take s = “awoaora”. We again find a palindrome “oao”. But we cant just append something in between. What I am trying to say is in the string “awoaora”, we know even if we add th string before “oao”, it make the string
  “awoaorawa”. Since we are appending only to the end, we cant do anything about the letters after palindrome, we can only deal with letters before it like in the previous example. So the only useful palindrome will be only if it exists at at the end. Since here no palindrome exists at the end, so we have add all letters except the last one as it will act as the middle letter. String will become “awoaoraroaowa”, which is a palindrome around a.

So our job is to find if a palindrome exists at the end of the string. Lets see how we can code it.

def minAppends(s):
        i = 0
        j = len(s) - 1
        match_index = -1  # index where palindrome starts
        while i< j:
            if s[i] == s[j]:
                if match_index == -1:
                    match_index = i
                j -= 1
            else:
                j = len(s) - 1 
                match_index = -1
            i += 1
        print(match_index)
        if match_index == -1:
            return len(s)-1
        return match_index

I have tried to make a dry run visual representation, please tell me if it is helpful.

For a string "abede", what will be the minimum number of appends for a palindrome. i = 0, j = len(s)-1,
match_index=-1
a  b  e  d  e
i           j
i        j
      i     j
         ij
a   b   s   s   a   x   y   z   a
i                               j
    i                       j<---  # match
        i                   --->j  # not match
            i                   j
                 i              j
                    i       j<---  # match
                        i   --->j  # not match
                            i   j
                            j   i
a   b   s   s   a   x   y   x   a                  match_index
i                               j                       -1
    i                       j<---  # match              1
        i                   --->j  # not match          -1
            i                   j                       -1
                i               j                       4
                    i       %%j                         4
                        ij                               break
                        
                        
                        return len(s)-match_index

Thanks. I hope I made it clear.