Time Complexity

If n is the length of the input string, then the time complexity for the algorithm described here is O(n). This is evident from the described algorithm, which traverses the entire input string from left to right only once.

The space complexity of the algorithm is, however, O(A), where A is the size of the alphabet. Most of the time, the size of the alphabet is constant (26 for lower-case letters, 25 for all letters, and 256 for ASCII) and quite low compared to memory of a modern computer. So space complexity can be thought of O(1).

Concluding Remarks

In this challenge, we discussed a linear time algorithm for finding the shortest substring of a string such that the substring has no duplicate characters

In trade-off of very little memory, the algorithm is time-efficient. But if the alphabet is very large, a more efficient data structure, that consumes less space can be used. One possibility is a hash table that would only store the characters that occurred last in the string and not the entire alphabet.