LeetCode 3 的时间复杂度。无重复字符的最长子串

Question

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.

我的解决方案：

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

我知道这不是一个有效的解决方案，但我无法计算出它的时间复杂度。

我访问了字符串中的每个字符，但是对于每个字符，window 都会扩展，直到找到一个重复的字符。所以每个字符最终都会被多次访问，但不确定是否有足够的时间来证明 O(n²) 时间复杂度是合理的，显然，它比 O(n) 更糟糕。

Answer 1

如果您知道您的输入可以组成的字符集的大小，您可以声称该算法是 O(n)，因为您的 window 可以扩展的长度受到不同字符数的限制在遇到重复字符之前您可以忽略的字符数，这取决于您正在使用的字符集的大小，它本身是一些与字符串长度无关的常量。例如，如果您只处理小写字母字符，则算法为 O(26n) = O(n).

更准确地说，您可以说它在 O(n*(min(m,n)) 中运行，其中 n 是字符串的长度，m 是字符串字母表中的字符数。 min 的原因是，即使你以某种方式处理无限唯一字符的字母表，最坏的情况是你正在做一个双 for 循环到字符串的末尾。然而，这意味着如果可能的字符数你在字符串中可能遇到超过字符串的长度你有一个最坏的情况 O(n^2) 性能（当字符串的每个字符都是唯一的时发生）。

LeetCode 3 的时间复杂度。无重复字符的最长子串

Time Complexity for LeetCode 3. Longest Substring Without Repeating Characters

python

algorithm

time-complexity