Search code examples
algorithmpalindrome

Append new characters to a Palindrome. Efficient or Dynamic way to check if the new string still a Palindrome?


Say I have a palindrome s and I am going to keep appending characters at the end of s for fun. But I want to stop once s is no longer a palindrome.

Now I am lazy so I don't want to rescan s to determine if it is a palindrome every time when a new character is appended to s. I am wondering if there a faster way to formularize/check if the new s is a palindrome by utilizing that the fact that s is already a palindrome. I feel there is a way to utilize that information but I can't quite wrap my head around it.


I am stuck on my thinking process. so far I am trying to break things down into cases.

the palindrome s can be in two form: (|__M__| is a substring portion of s and |__-M__| is the reverse of |__M__|)

when the length is odd:

|__-M__|X|__M__|

when the length is even:

|__-M__||__M__|

now when I append the new character c is there an efficient way to check

|__-M__|X|__M__|c <---- a palindrome?

|__-M__||__M__|c <---- a palindrome?


Solution

  • Formalizing the same-character conjecture from the comments:

    If not all characters in the string S having N characters are the same, there must be:

    • a character C1 at index P1, followed by a different C2 at P1+1
    • a C1 at the mirror index N-1-P1, preceded by C2 at N-2-P1

    After adding any single character to S, now there must be:

    • a character C1 at index P1, followed by C2 at P1+1
    • a C1 at mirror index, now being N-P1, preceded by C2 at N-1-P1

    So, the character at N-1-P1 must be both C1 (before the extension) and C2 (after the extension) which is impossible as we said they are different.

    So, only if the original string is a repetition of one single charater, is it possible to extend it character-per-character and keep it being a palindrome.