LeetCode 第 3 题：最长不重复字符串

动态规划 滑动窗口 散列表

传送门：3. 无重复字符的最长子串。这道题也是《剑指Offer》上第 48 题。

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解法1：哈希表 + 隔板法（好几种写法）

判断一个元素有没有出现过，使用哈希表是最自然的想法。

以下面的例子进行说明：

判断连续区间内是否出现重复元素，可以使用 set，又要存储位置，所以使用 dict。

• 到索引为 $3$ 的时候，出现重复，我们可以在 $a$ 的下一个位置插一个“小木板”，表示从这个“小木板”到当前位置没有重复。如果出现重复的索引在“小木板”之前，例如到索引 $4$ 的时候，此时“小木板”在索引 $2$ 处，两个 $d$ 之间已经有了两个 $a$ ，可以无视这种情况。

Python 代码1：（推荐写法）

等价的写法：（我的练习）

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        map = dict()
        max_len = 0
        # 可以认为是标定的起始
        pointer = 0
        for index, c in enumerate(s):
            if c in map:
                pointer = max(pointer, map[c] + 1)
            max_len = max(max_len, index - pointer + 1)
            # 每次遍历都更新当前遍历到的字母的位置
            map[c] = index
        return max_len
if __name__ == '__main__':
    s = 'pwwkew'
    solution = Solution()
    result = solution.lengthOfLongestSubstring(s)
    print(result)

需要注意的一点是：只有重复出现的位置大于标定点的时候，才要更新，更新的位置是当前位置 + 1。即只要出现重复，隔板就向后移动一位，然后每一轮都计算当前与隔板的距离。

Python 代码2：（不如上面的代码语义清晰）

class Solution:
    def lengthOfLongestSubstring(self, s):
        # 特判
        l = len(s)
        if l < 2:
            return l
        # 隔板法
        # key:字符，val 出现的索引
        map = dict()
        point = 0
        res = 1
        for i in range(l):
            # 关键1：map[s[i]] >= point，等于是可以的
            if s[i] in map and map[s[i]] >= point:
                # 先把隔板向后移动一位
                point = map[s[i]] + 1
            # 然后记录最长不重复子串的长度
            res = max(res, i - point + 1)
            # 关键2：无论如何都更新位置
            map[s[i]] = i
        return res

等价的写法：（我的练习）

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        l = len(s)
        if l <= 1:
            return l
        point = 0
        map = dict()
        result = 0
        for index, alpha in enumerate(s):
            if alpha in map and map[alpha] >= point:
                point = map[alpha] + 1
            # 每次要做两件事：1、计算无重复子串长度
            result = max(result, index - point + 1)
            # 2、更新索引
            map[alpha] = index
        return result

解法2：动态规划

dp[i]：以 s[i] 结尾的最长不重复子串，这个状态的设置与最长上升子序列、最大连续子数组是一样的。

下面考虑 dp[i] 和 dp[i-1] 之间的关系。关键在于 dp [i-1] 与距离出现相同字符的时候，两个相同字符的距离的比较。

Python 代码：

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        # 特判
        l = len(s)
        if l < 2:
            return l
        # dp[i] 表示以 s[i] 结尾的最长不重复子串的长度
        # 因为自己肯定是不重复子串，所以初始值设置为 1
        dp = [1 for _ in range(l)]
        map = dict()
        map[s[0]] = 0
        for i in range(1, l):
            if s[i] in map:
                if i - map[s[i]] > dp[i - 1]:
                    dp[i] = dp[i - 1] + 1
                else:
                    dp[i] = i - map[s[i]]
            else:
                dp[i] = dp[i - 1] + 1
            # 设置字符与索引键值对
            map[s[i]] = i
        # 最后拉通看一遍最大值
        return max(dp)

解法3：滑动窗口、双指针

Python 代码：推荐写法

# 滑动窗口的做法
class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        # 特判
        size = len(s)
        if size < 2:
            return size
        l = 0
        r = -1
        counter = [0 for _ in range(256)]
        res = 1
        while l < size:
            # 尝试走一步，如果可以走，就计算
            if r + 1 < size and counter[ord(s[r + 1])] == 0:
                # 表示没有重复元素，r 可以加 1
                counter[ord(s[r + 1])] += 1
                r += 1
            else:
                # 有重复元素，左边就要减 1
                counter[ord(s[l])] -= 1
                l += 1
            res = max(res, r - l + 1)
        return res

Python 代码：滑动窗口写法2

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        # 特判
        size = len(s)
        if size < 2:
            return size
        l = 0
        r = -1
        counter = [0 for _ in range(256)]
        res = 1
        while l < size:
            # 首先"右指针"不断向右边尝试，走到出现重复的最右边
            while r + 1 < size and counter[ord(s[r + 1])] == 0:
                # 表示没有重复元素，r 可以加 1
                counter[ord(s[r + 1])] += 1
                r += 1
            # 此时，记录不重复子串是"左指针"固定时候最长
            res = max(res, r - l + 1)
            # 考虑移动"左指针"
            # 此时 s[r+1] 就是已经扫过的区间里重复的元素，要把它剔除出去
            while r + 1 < size and s[l] != s[r + 1]:
                # 有重复元素，左边就要减 1
                counter[ord(s[l])] -= 1
                l += 1
            # 出了上一个循环以后，还要再把左指针向右移动一格，否则右指针不能向右移动
            counter[ord(s[l])] -= 1
            l += 1
        return res

（本节完）