Problem: Given a string s, find the length of the longest substring without repeating characters.

Example: Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.

My solution:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        seen = set()
        l = r = curr_len = max_len = 0
        n = len(s)
        
        while l < n:
            if r < n and s[r] not in seen:
                seen.add(s[r])
                curr_len  = 1
                max_len = max(curr_len, max_len)
                r  = 1
            else:
                l  = 1
                r = l
                curr_len = 0
                seen.clear()
                
        return max_len

I know this is not an efficient solution, but I am having trouble figuring out its time complexity.

I visit every character in the string but, for each one of them, the window expands until it finds a repeated char. So every char ends up being visited multiple times, but not sure if enough times to justify an O(n²) time complexity and, obviously, it's way worse than O(n).

CodePudding user response：

You could claim the algorithm to be O(n) if you know the size of the character set your input can be composed of, because the length your window can expand is limited by the number of different characters you could pass over before encountering a duplicate, and this is capped by the size of the character set you're working with, which itself is some constant independent of the length of the string. For example, if you are only working with lower case alphabetic characters, the algorithm is O(26n) = O(n).

To be more exact you could say that it runs in O(n*(min(m,n)) where n is the length of the string and m is the number of characters in the alphabet of the string. The reason for the min is that even if you're somehow working with an alphabet of unlimited unique characters, at worst you're doing a double for loop to the end of the string. That means however that if the number of possible characters you can encounter in the string exceeds the string's length you have a worst case O(n^2) performance (which occurs when every character of the string is unique).