Hint for true O(N) solution

  • 0

    You can make your solution expected time O(N) by implementing expected O(1) isPalindrome() and using it in a DP algorithm similar to what have been already proposed.
    The hint is to use hashing like in Rabin-Karp string matching.
    With O(N) space you can create hashes of all prefixes of the string and hashes of all suffixes (with a hash computed in a reverse direction). This data structure will allow to retrieve a hash of any substring of the string in O(1) time as well as a hash of the substring in a reverse direction. This will allow to quickly prove that specific substring is not a palindrome and fall-back into expensive checking only if hashes match.
    If you select a really good hash function you can even rely on the hash-based comparison only and construct a potential answer in pure Theta(N) time and only at the end check if the answer is a palindrome. If it is palindrome then it must be the longest one, if not then you can re-start algorithm with strong verification of palindromes.
    By making hash function parameters randomized you prevent constructing the worst case of the whole algorithm, making it expected O(N) time.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.