If you hand code your own hash function you can compute hash(string with zeroed out i-th character) from hash(string) in O(1) An example of such a hash is a po

If you hand code your own hash function you can compute hash(string with zeroed out i-th character) from hash(string) in O(1) An example of such a hash is a polynomial hash (sum c_i * p^i modulo M, with p and M prime) such as the one used to explain https://en.m.wikipedia.org/wiki/Rabin–Karp_algorithm https://en.m.wikipedia.org/wiki/Rabin–Karp_algorithm