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?