[剑指 Offer 第 2 版第 48 题] “最长不重复字符串的子字符串”做题记录

第 48 题：最长不重复字符串的子字符串

传送门：最长不含重复字符的子字符串。

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

假设字符串中只包含从’a’到’z’的字符。

样例：

输入："abcabc"

输出：3

思路1：滑动窗口：

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:
                # 首先"右指针"不断向右边尝试，走到出现重复的最右边
                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

思路2：动态规划

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):
            # 特判
            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

参考资料：LeetCode 第 3 题：最长不重复字符串。

作者：liweiwei1419

来源：https://liweiwei1419.github.io/sword-for-offer/