Online Palindrome Check in a Character Stream
Problem statement
Characters arrive one at a time in a stream. After each new character, report whether the entire string received so far reads the same forwards and backwards (is a palindrome). You cannot rescan the whole prefix on every arrival -- that would be $O(n^2)$ overall.
Implement the function:
def palindrome_stream(s):
...
It receives the full string s (whose characters you process left-to-right as if they were streaming in) and returns a list of booleans of length len(s) -- element i is True iff the prefix s[0..i] is a palindrome.
Constraints:
- Characters arrive online; you see $s[i]$ before $s[i+1]$ and cannot look ahead.
- After appending each character, output
true/falsefor the current prefix. - Target $O(1)$ amortized work per character (a full rescan per character is disallowed).
Example
palindrome_stream("aba") -> [True, False, True]
After a the prefix "a" is a palindrome (True); after b the prefix "ab" is not (False); after the final a the prefix "aba" reads the same both ways (True).
Show hint
What compact summary of a string can be updated in constant time when one character is appended?
Relevant roles: ML Engineer, AI Engineer, LLM Engineer and Forward Deployed Engineer.