LeetCode 3 Longest Substring Without Repeating Characters

一、题目链接

https://leetcode.com/problems/longest-substring-without-repeating-characters/

二、解答

2.1 解法一，暴力求解

直接使用暴力方法，遍历所有可能的子串，并判断是否有重复的字符，当没有重复的字符时，计算其长度，然后取最长的字符串的长度即为最后的结果。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        def check(start, end):
            chars = [0] * 128
            for i in range(start, end + 1):
                c = s[i]
                chars[ord(c)] += 1
                if chars[ord(c)] > 1:
                    return False
            return True

        n = len(s)
        res = 0
        for i in range(n):
            for j in range(i, n):
                if check(i, j):
                    res = max(res, j - i + 1)
        return res

时间复杂度：\(O(N^3)\)，N 为字符串的长度。 空间复杂度：我认为是 \(O(1)\)，因为每一次 check，需要 128 个空间，这是一个常数单位。但是官方教程说是 O(min(m, n))，其中 m 是 128，n 是字符串的长度，我认为应该是错误的。

2.2 滑动窗口

直接看代码

class Solution2:
    def lengthOfLongestSubstring(self, s: str) -> int:
        chars = [0] * 128
        left = right = 0
        res = 0
        while right < len(s):
            r = s[right]
            chars[ord(r)] += 1
            # chars[r] > 1 表明从 left 到 right 之间出现重复的字符了
            while chars[ord(r)] > 1:
                l = s[left]
                chars[ord(l)] -= 1
                left += 1
            res = max(res, right - left + 1)
            right += 1
        return res

这里主要的思想是利用 left 和 right 这两个指针，

• 先固定 left 指针，然后滑动 right 指针，
• 如果在 left 到 right 之间的子串中出现了重复的字符，那么，这时就固定 right 指针，
• 然后移动左指针，直到 left 到 right 之间的子串中没有重复的字符。

这里有一个 Python 函数要说明一下，

• ord(): Return the Unicode code(ASCII code) point for a one-character string.

时间复杂度：\(O(N)\)，left 指针和 right 指针在最坏情况下，总计会遍历字符数组两遍。 空间复杂度：同解法一的空间复杂度。

2.3 解法三 滑动窗口优化

直接看代码

使用字典的版本

class Solution3:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        ans = 0
        # 存储字符最后一次出现的索引，然后加一
        mp = {}
        i = 0
        for j in range(n):
            if s[j] in mp:
                i = max(mp[s[j]], i)
            ans = max(j - i + 1, ans)
            mp[s[j]] = j + 1
        return ans

说一下 line8 和 line9 代码的含义，这里是判断 j 指向的字符是否在 mp 字典中，如果在，说明之前出现过了这个字符，但是，出现过的字符有两种情况

• 第一种，重复的字符在索引 i 到 j（不含 j）之间，那么 line9 这行代码就会把 i 指针移动到 mp[s[j]] 位置处（注意 line11 这行代码），
• 第二种，重复的字符在索引 i 之前出现，这个对索引 i 到索引 j 之间的子串没有影响，因而，line9 执行完之后 i 的值不变。

使用列表的版本

class Solution3_2:
    def lengthOfLongestSubstring(self, s: str) -> int:
        chars = [None] * 128
        left = right = 0
        res = 0
        while right < len(s):
            r = s[right]
            index = chars[ord(r)]
            # 出现重复的字符了
            if index != None and index >= left and index < right:
                left = index + 1
            res = max(res, right - left + 1)
            chars[ord(r)] = right
            right += 1
        return res

这里的 line10 和 line11 两行代码和上面的使用字典的代码的 line8 和 line9 两行代码的作用相同。

时间复杂度：\(O(N)\)。 空间复杂度：我认为还是 \(O(1)\)。其实争执这个没什么意义。

三、完整代码

# -*- coding: utf-8 -*-
# @File  : leet_03.py
# @Author: FanyFull
# @Date  : 2021/7/10

# 暴力解法
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        def check(start, end):
            chars = [0] * 128
            for i in range(start, end + 1):
                c = s[i]
                chars[ord(c)] += 1
                if chars[ord(c)] > 1:
                    return False
            return True

        n = len(s)
        res = 0
        for i in range(n):
            for j in range(i, n):
                if check(i, j):
                    res = max(res, j - i + 1)
        return res

# 滑动窗口
class Solution2:
    def lengthOfLongestSubstring(self, s: str) -> int:
        chars = [0] * 128
        left = right = 0
        res = 0
        while right < len(s):
            r = s[right]
            chars[ord(r)] += 1
            # chars[r] > 1 表明从 left 到 right 之间出现重复的字符了
            while chars[ord(r)] > 1:
                l = s[left]
                chars[ord(l)] -= 1
                left += 1
            res = max(res, right - left + 1)
            right += 1
        return res

# 滑动窗口优化
class Solution3:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        ans = 0
        mp = {}
        i = 0
        for j in range(n):
            if s[j] in mp:
                i = max(mp[s[j]], i)
            ans = max(j - i + 1, ans)
            mp[s[j]] = j + 1
        return ans

class Solution3_2:
    def lengthOfLongestSubstring(self, s: str) -> int:
        chars = [None] * 128
        left = right = 0
        res = 0
        while right < len(s):
            r = s[right]
            index = chars[ord(r)]
            # 出现重复的字符了
            if index != None and index >= left and index < right:
                left = index + 1
            res = max(res, right - left + 1)
            chars[ord(r)] = right
            right += 1
        return res

if __name__ == '__main__':
    solution = Solution3_2()
    s = 'abcdeabcd'
    print(solution.lengthOfLongestSubstring(s))