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?
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:
C1
at index P1
, followed by a different C2
at P1+1
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:
C1
at index P1
, followed by C2
at P1+1
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.