leetcode-three | Longest Substring Without Repeating Characters

3. 无重复字符的最长子串（Longest Substring Without Repeating Characters）

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.

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

示例 1:

输入: “abcabcbb”

输出: 3

解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

解决方案

方法一：暴力法

思路

逐个检查所有的子字符串，看它是否不含有重复的字符。

• 假设开始和结束的索引分别为 i 和 j。那么我们有 0 ≤ i < j ≤ n 。因此，使用 i 从0到 n - 1以及 j 从 i+1 到 n 这两个嵌套的循环，我们可以枚举出 s 的所有子字符串。
• 要检查一个字符串是否有重复字符，我们可以使用集合。我们遍历字符串中的所有字符，并将它们逐个放入 set 中。在放置一个字符之前，我们检查该集合是否已经包含它。如果包含，我们会返回 false。循环结束后，我们返回 true。

leetcode给的参考代码：

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j <= n; j++)
                if (allUnique(s, i, j)) ans = Math.max(ans, j - i);
        return ans;
    }

    public boolean allUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        for (int i = start; i < end; i++) {
            Character ch = s.charAt(i);
            if (set.contains(ch)) return false;
            set.add(ch);
        }
        return true;
    }
}
           

仿造一个python的：

class Solution:
    def lengthOfLongestSubstring(self, s):
        def unique(s, i,j):
            se = set()
            while i<j:
                if s[i] in se:
                    return False
                se.add(s[i])
                i+=1
            return True

        res = 0
        for i in range(len(s)):
            j = i+1
            while j<=len(s):
                if unique(s,i,j):
                    res = max(res, j-i)
                j+=1

        return res
           

但是实际上，是运行超时的。

（986 / 987 个通过测试用例）

时间复杂度：

O(n^3)

。

方法二：滑动窗口

暴力法非常简单。但它太慢了。那么我们该如何优化它呢？

在暴力法中，我们会反复检查一个子字符串是否含有有重复的字符，但这是没有必要的。如果从索引 i 到 j - 1之间的子字符串 sij已经被检查为没有重复字符。我们只需要检查 s[j] 对应的字符是否已经存在于子字符串 sij中。

要检查一个字符是否已经在子字符串中，我们可以检查整个子字符串，这将产生一个复杂度为 O(n^2) 的算法，但我们可以做得更好。

通过使用 HashSet 作为滑动窗口，我们可以用 O(1)的时间来完成对字符是否在当前的子字符串中的检查。

例如，我们将 [i, j)向右滑动 1 个元素，则它将变为 [i+1,j+1)（左闭，右开）。

我们使用 HashSet 将字符存储在当前窗口 [i, j)（最初 j = i）中。 然后我们向右侧滑动索引 j，如果它不在 HashSet 中，我们会继续滑动 j。直到 s[j] 已经存在于 HashSet 中。此时，我们找到的没有重复字符的最长子字符串将会以索引 i 开头。如果我们对所有的 ii 这样做，就可以得到答案。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            // try to extend the range [i, j]
            if (!set.contains(s.charAt(j))){
                set.add(s.charAt(j++));
                ans = Math.max(ans, j - i);
            }
            else {
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }
}
           

python仿写如下，思想很好，使用滑动窗口。从0开始判断，如果在集合中，我们除去首位，此时j指针并不后移，所以判断的还是上一次判断的位置，此时再次判断，存在集合中，还是除去首位，也就是缩减窗口大小。：

class Solution:
    def lengthOfLongestSubstring(self, s):
        se = set()
        ans, i,j=0,0,0
        while i<len(s) and j<len(s):
            if s[j] not in se:
                se.add(s[j])
                j+=1
                ans = max(ans, j-i)
            else:
                se.remove(s[i])
                i+=1   #每次i移动一位
        return ans

if __name__ == '__main__':
    b = Solution().lengthOfLongestSubstring("afabcad")
    print(b)
           

但是，还是不理想。

执行用时 : 212 ms, 在Longest Substring Without Repeating Characters的Python3提交中击败了26.50% 的用户

内存消耗 : 13.2 MB, 在Longest Substring Without Repeating Characters的Python3提交中击败了59.81% 的用户

987 / 987 个通过测试用例

状态：通过

执行用时：212 ms

时间复杂度：

O(2n) = O(n)

方法三：优化的滑动窗口

上述的方法最多需要执行 2n 个步骤。事实上，它可以被进一步优化为仅需要 n 个步骤。我们可以定义字符到索引的映射，而不是使用集合来判断一个字符是否存在。 当我们找到重复的字符时，我们可以立即跳过该窗口。

也就是说，如果 s[j] 在 [i, j) 范围内有与 j’重复的字符，我们不需要逐渐增加 i 。 我们可以直接跳过 [i，j’]范围内的所有元素，并将 i 变为 j’ + 1 。

Java代码：

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>(); 
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }
}
           

python 仿造：

class Solution:
    def lengthOfLongestSubstring(self, s):
        se = dict()
        ans, i, j = 0, 0, 0
        while j<len(s):
            if s[j] in se:
                i = max(i, se[s[j]]) #i等于se[s[j]]时，也就是上一个j'，需要变成j'+1为下一个窗口的起始位置，这里也可以：i = max(i, se[s[j]]+1)
                #print(i)
            ans = max(ans, j-i+1) #当判断是“a”一个字符的时候，j-i=0-0=0，而实际上是1,故而加入j-i+1
            se.update({s[j]:j+1}) # j'+1放入了这里，做了统一处理，使字典中所有的元素都加1，使得下标从1开始
            #print(se)
            j+=1
        return ans
           

结果：

执行用时 : 192 ms, 在Longest Substring Without Repeating Characters的Python3提交中击败了29.89% 的用户

内存消耗 : 13.1 MB, 在Longest Substring Without Repeating Characters的Python3提交中击败了96.90% 的用户

时间复杂度：

O(n)

虽然比上一个执行效率要好一些，但这里的执行效率还是不怎么高，这就可能是我自己程序的问题了。

方法四：

LeetCode上给出了，二天再考虑。

作者：无涯明月

原文地址：http://baiyazi.top/2019/leetcode-3