DEV Community


Discussion on: The Longest Palindromic Substring: Solving the Problem Using Constant Space

hkrogstie profile image
Håvard Krogstie • Edited

Nice post, made me think if there are asymptotically faster options. The best I could do was O(n log n) by binary searching and doing polymorphic hashing, which is only probibalistic. It would only give false positives though, so you could check. You did specify a max length, though, so O(n^2) is maybe even faster in this case, if the loops are unrolled and cache is good or something.