This is a problem that I've been thinking of for quite a while.

You start with the empty string. There will be $$$q$$$ queries. Each query will append a character to the string. You have to answer if the new string is a palindrome.

• "" — add A ----> "A" = True
• "A" — add B ---> "AB" = False
• "AB — add A ---> "ABA" = True
• .... and so on for $$$q$$$ steps.

Is there an efficient (better than $$$O(q^2)$$$) online solution for this problem?