> A palindrome check on this object will take O(1) time for false and O(n) time for true.<p>Someone correct me if I'm wrong, but this sounds like a suspicious statement to me. If the false case is constant time, then the true (not false) case should also be constant time. In reality, I think the statement should be something like "the palindrome check runs in O(n) time", but that may ruin the overall runtime by my understanding.<p>I have not looked closely at the implementation.<p>Ok, I thought about it some more and I think the usage of Big-O in that sentence is what confused me. The comparison of two hashes is constant time is my takeaway. The key point of this approach is that it replaces the linear string comparison with the comparison of rolling hashes if I understand correctly, which makes it faster. Sounds relatively unique - as in a nice approach that's non-textbook.<p>I believe this kind of thinking is what these kinds of interviewing questions are supposed to look for, rather than regurgitating memorized answers (and pretending you came up with them). But the difficulty spiked due to people gaming the interview which ruined it for the normal non-leetcode-prep engineers.