n is the number of characters in the string in this case. If you had a function that could turn a string into a hash key in O(1) then you could look that key up in a hash in O(1). However, you need to go through the string one character at a time[1] so you can’t. This is exactly why tries/prefix trees exist (although they aren’t only relevant for strings).

[1] This seems to me to be a practical limitation rather than theoretical given strings and numbers are really equivalent - it’s just that the space is mindbogglingly huge so if you wanted to do a general purpose O(1) string to number conversion it would require uncountably infinite space.

Assuming that the dictionary is arbitrary as well, just comparing the string to the strings in the dictionary (or hashing it) it takes O(n), regardless of the data-structure you use.

Is that relevant to real-world use? You mention Python in TFA - I'm no expert but I believe it does string interning, and caches the results of string hashes, which would suggest real-world performance should be constant over time in both cases.