Actually, the hash based solution is roughly O(length) time. It's (approximately) a constant amount of time to insert/index into the hash, and you only iterate over the string once.