3 ms·
Interesting, I didn't consider the hash collision angle, as I figured they're normally rare enough to discard as part of average runtime calculations. It does
by thdc 4y ago
Interesting, I didn't consider the hash collision angle, as I figured they're normally rare enough to discard as part of average runtime calculations.
It does seem to line up with the explanation of the algorithm though - the less candidate palindromes the better as it enters the linear runtime branch less often.
I'm not well versed on hash collisions but I imagine it's kind of awkward to do in this scenario - the strings will have to initially be palindromes themselves to get to a decent length to scale the comparison's runtime (why compare str1 + x and str2 + y when str1 and str2 don't match). As posted towards the end of tfa, an example worst case in put is something like aaaaaaaaaaaaaa.
- ithkuil 4y agoUnless you want your algorithm to produce wrong results sometimes, you have to check whether two strings are sctually equal even if you know they are really likely to br equal (since they hash to the same value)
- krackers 4y agoThat's true, but practically when you do this you can just say the probability of a false positive is bounded above by 1/1e5 or so and you just ignore it, because most likely the only reason you care about the longest palindromic substring in the first place is to pass the leetcode autograder. Edit: For a more rigorous proof of the error bound, see https://baites.github.io/algorithms/algorithm-analysis/2020/03/23/string-hashing-and-palindromes.html https://baites.github.io/algorithms/algorithm-analysis/2020/... Basically it's O(n)/P where P is your prime modulus (usually 1e6 + 3 or 1e9 + 9), so for most practical input lengths your probability of collision is negligibly small enough that you'll pass the autograder).