无重复字符的最长子字符串

Question

我在Longest Substring Without Repeating Characters - LeetCode上花了好几个小时

3. Longest Substring Without Repeating Characters

Medium

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

Example 1:

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

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

这个问题可以用两个指针混合的kadane算法来处理子阵

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        logging.debug(f"{list(enumerate(s))}")
        slo = fas = 0  #slow as the fisrt character in a subarray which not duplicate, fast as the fast.
                                  #relation: length = fas - slo
        current = set()
        glo = loc = 0
        while fas < len(s):
            logging.debug(f"pre_current: {current}, slow: {slo}, fast: {fas}")
            if s[fas] not in current: 
                current.add(s[fas]
                loc = fas - slo
                glo = max(glo, loc)
                 fas +=1
            else:
                current.remove(s[slo])
                slo += 1
            logging.debug(f"post_current: {current}, slow: {slo}, fast: {fas} \n")
        return glo

测试用例

^{pr2}$

解决方案很清楚，可以慢一点和快一点交替进行

$ python 3.LongestSubstring.py MyCase.test_g
DEBUG [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'c'), (4, 'e'), (5, 'f'), (6, 'g')]
DEBUG pre_current: set(), slow: 0, fast: 0
DEBUG post_current: {'a'}, slow: 0, fast: 1 

DEBUG pre_current: {'a'}, slow: 0, fast: 1
DEBUG post_current: {'b', 'a'}, slow: 0, fast: 2 

DEBUG pre_current: {'b', 'a'}, slow: 0, fast: 2
DEBUG post_current: {'b', 'c', 'a'}, slow: 0, fast: 3 

DEBUG pre_current: {'b', 'c', 'a'}, slow: 0, fast: 3
DEBUG post_current: {'b', 'c'}, slow: 1, fast: 3 

DEBUG pre_current: {'b', 'c'}, slow: 1, fast: 3
DEBUG post_current: {'c'}, slow: 2, fast: 3 

DEBUG pre_current: {'c'}, slow: 2, fast: 3
DEBUG post_current: set(), slow: 3, fast: 3 

DEBUG pre_current: set(), slow: 3, fast: 3
DEBUG post_current: {'c'}, slow: 3, fast: 4 

DEBUG pre_current: {'c'}, slow: 3, fast: 4
DEBUG post_current: {'c', 'e'}, slow: 3, fast: 5 

DEBUG pre_current: {'c', 'e'}, slow: 3, fast: 5
DEBUG post_current: {'e', 'f', 'c'}, slow: 3, fast: 6 

DEBUG pre_current: {'e', 'f', 'c'}, slow: 3, fast: 6
DEBUG post_current: {'g', 'e', 'f', 'c'}, slow: 3, fast: 7 

.
----------------------------------------------------------------------
Ran 1 test in 0.001s

综上所述，该方案采用了双指针技术和Kadane算法的思想。我假设在作为一个初学者花了几个小时调试之后，最终有可能解决这个问题。在

然而，我读到了这样一个微妙的解决方案

class SolutionA:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        #slow is the first  which not duplicate in a subarray
        #fast is the last whichi not duplicate in a subarray
        lookup, glo, slo, fas = {}, 0, 0, 0
        for fas, ch in enumerate(s):
            if ch in lookup: 
                slo = max(slo, lookup[ch]+1)
            elif ch not in lookup:
                glo = max(glo, fas-slo+1)                
            lookup[ch] = fas #update the duplicates and add new 
        return glo

这个解决方案非常聪明，我真的不相信一个人能在几个小时内设计出这样一个解决方案，如果你以前没有读过它。在

它采用了hash映射，两倍于kadane算法的思想和非常简洁的结构。在

这是一种常用的双指针技术吗？它叫什么名字

Answer 1

如第二种方法中对解决方案的评论所述：

slow is the first which not duplicate in a subarray

fast is the last which is not duplicate in a subarray

它使用2个指针来跟踪没有重复字符的窗口大小。如果找到重复项，它会相应地更新指针。在

换句话说，它维护一个窗口，并进一步滑动它们，以查看它与non-repeating characters属性一起使用多长时间。所以，这个方法被称为sliding window technique。在

对于只有26个字母字符的字符串来说，这可能看起来微不足道，但对于UTF-8类型的字符串来说，这非常有用。在