Leetcode longest substring with no duplicates class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        longest = ''
        max_len = 0
        for key,value in enumerate(s):
            if value in longest:
                longest = longest[longest.index(value)+1:] + value
            else:
                longest+=value
            max_len = max(max_len,len(longest))
        return max_len                



Here is my solution for leetcode's "longest-substring-without-repeating-characters question". I don't quite understand why my time complexity is so efficient (99% out of all python submissions). Since strings are immutable in python, assuming a strength of length n, won't my algorithm be $$ 1+2+3+...n-1+n = O(n^2)$$ time? But the optimal solution is on \$O(n)\$ yet the runtime from the testcases says my solution is just as good as the optimal one provided?Am I missing something. Also I am having a hard time proving the space complexity for my solution as well.
The linearity of your approach is due to the fact that your longest could never be longer than the size of the alphabet (otherwise it'd have a duplicate for sure). It means that your code runs at \$O(N * A)\$, where \$N\$ is a length of the string, and \$A\$ is a size of alphabet. Since the latter is a constant, you may safely take it out of the big-O, yielding \$O(N)\$.

The asymptotic constant is still a little bit too large (I don't know what alphabet is used in the test cases, but it is safe to assume at least 26), so there is a room for improvement. You correctly noticed that the immutability of the strings may hurt performance; try to get rid of them. A most obvious approach is to preallocate a list (of the alphabet size), and use it as a circular buffer.

In fact, even that is suboptimal. Try to get rid of the explicit buffer at all (hint: two indices into the original string).

It also may be beneficial to keep a dictionary indexed by letters currently present in the buffer with the values being their corresponding indices. This way you can do a constant time lookup rather than linear search in the buffer. Keep in mind however that such a dictionary may itself be costly; I expect it to improve performance if the alphabet is quite large. Try and profile it.

As for the code, it is simple and clean. Not much to say.