Identifying Palindromes Online

Revision en1, by proofbycontradiction, 2019-04-09 15:50:01

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?

Tags #strings, #palindrome, #online

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English proofbycontradiction 2019-04-09 15:50:01 498 Initial revision (published)