> He was asking about the complexity in relation to the size of the input string,
But you don't try checking if the entire string is in the dictionary regardless of n - you only ever check if it's in the dictionary if it's shorter than X+1 where X is the longest string in the dictionary. As the input string size grows, the dictionary lookups are capped.
The underlying issue here is that TFA doesn't describe having a discussion about the complexity.
If the author asked about complexity as an open-ended question with no fixed answer, that would be a very reasonable way to hear how the candidate thinks about algorithms. But TFA makes it clear that the author treats it as a gotcha question - he expects candidates to say o(n) and then pushes them to give the answer he wants. That's not a great approach, even if the interviewer's preferred answer is unambiguously correct - and here it's not.
