# O(1) Space O(N) Time Python Solution Based on Polynomial Hashing

• The key is to find a way to do high efficient string matching.
Most solution are based on O(N) space KMP algo. Here I present another O(1) space solution.

Define a string's polynomial function as

``````Hash(s) = (c0*p^n + c1*p^(n-1) + ... cn) % m
``````

Therefore, it's O(1) to update the hash value when modify front or tail character.

To demonstrate how does it work, let's play with an input like 'babcd'.

Firstly, an O(N) Initialization

``````forward = hash('babcd')
reverse = hash('dcbab')
``````

Then we remove the tail from forward and head from reversed, update the hash value.

``````Iteration 1:  hash('babcd') != hash('dcbab')
Iteration 2:  hash('babc') != hash('cbab')
Iteration 3:  has('bab') == hash('bab')
``````

Each iteration is O(1), so the overall complexity is O(N). And we only used two variables here:)

``````class Solution:
# @param {string} s
# @return {string}
def shortestPalindrome(self, s):
prime = 7
modular = 1000
length = len(s)

forward = reverse = 0
power = 1
for i in range(length):
forward = (forward * prime + ord(s[i])) % modular
reverse = (reverse * prime + ord(s[length - i -1])) % modular
power = power * prime % modular if i > 0 else power

forward_power = 1
for i in range(len(s)):
if forward == reverse:
tmp = s[:len(s)-i]
if tmp == tmp[-1::-1]:
return s[len(s)-i:][-1::-1] + s
pass
# Remove tail from forward
forward -= ord(s[len(s)-i-1]) * forward_power % modular
forward = forward + modular if forward < 0 else forward
forward_power *= prime

# Remove head from reverse
reverse -= ord(s[len(s)-i-1]) * power % modular
reverse = reverse + modular if reverse < 0 else reverse
reverse = reverse * prime % modular

return s[::-1] + s[1:]``````

• Interesting approach. Some comments/questions:

• `c2*p(n-1)` is missing `^`. And you start with `c1*p^n` and end with `cn*p^0`, that's an off-by-1 error.
• What's the `pass` for? It doesn't do anything.
• Why start the powers with 1, 1, 7, 49 instead of 1, 7, 49?
• In each operation, you don't just change `forward` and `reverse` but potentially create and check a long substring, so it's not O(1) but O(n).

• Thank you for pointing out the typo. The hash function is updated.

The pass is a placeholder there, because I implemented the "update" part below then came back and finished the "return" part.

For the reason "power" is begin with 1, 1, 7, 49. It's because the power is used for removing the head from "reverse" hash.

A comparison is only required when found result or hash function collision. With a bigger prime and modular, we pass the test even without the verification. Try Prime=17, Modular=1000000.

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