LeetCode 3. Longest Substring Without Repeating Characters 无重复字符的最长子串[Medium]

发表于 | 更新于 | 分类于 ， | 阅读次数：

题目来源：

中文版：3. 无重复字符的最长子串 - 力扣（LeetCode）

英文版：https://leetcode.com/problems/longest-substring-without-repeating-characters/

题目难度：Medium

答题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
最笨的办法就是暴力算法
枚举出所有子串，然后一个一个判定，如果有重复的去掉，最后从中取出最长的子串。如果有重复的，就全部都输出。
如果题目保证只有一个，那最终答案就只有一个。


方案2
优化一下方案就是

可以边找边判断，从每一个索引出发，判断从当前索引开始，能够找到的最长的子串
一边找，一遍把已经出现过的字符保存起来，当遇到重复字符的时候，记录下来当前的子串及其长度。
然后切换到下一个索引再开始判断。

同时，如果遍历到一半的时候，如果判断剩下的最大子串长度都比当前已经找到的最长子串长度还要小，就可以提前结束遍历。


方案3

在方案2中，我们想到了每次遇到重复的字符的时候，就从下一个索引开始遍历，但是
这里其实还可以优化一下，我们从下一个索引开始遍历的时候，不需要完全再从头开始遍历，
因为之前可能已经遍历过一部分了，只需要在遇到重复的元素的时候，把最开头的元素舍弃掉，就相当于是
从下一个索引位置一直遍历到当前位置了。这种思想就被称为滑动窗口。

当下一个元素和之前遇到的某个元素相同的时候，那么当前的元素和之前已经遇到的元素只能保留一个。
需要把索引移动到上次遇到的相同的元素的下一个元素，然后继续。

假如遇到两个连续的字符，那么相当于要从头开始计算了。

方案4
由于只要求最长子串，每次遍历到一个位置的时候，肯定有一个子串开始的索引
我们只要记录下来子串最开始位置的索引，然后从当前位置即可算出子串的长度

解答1[Java]：滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.isEmpty()) {
            return 0;
        }

        int[] frequencies = new int[256];
        int left = 0;
        int right = -1;
        int maxSubstringLength = 0;

        while (left < s.length() && (right + 1) < s.length()) {
            char c = s.charAt(right + 1);
            if (frequencies[c] == 0) {
                ++right;
                frequencies[c] = 1;
            } else {
                char c1 = s.charAt(left);
                frequencies[c1]--;
                ++left;
            }
            maxSubstringLength = Math.max(maxSubstringLength, right - left + 1);
        }

        return maxSubstringLength;
    }
}

根据出现频率来的，只要右指针当前指向的字符串出现的频率不是 0 次，左指针就继续向右移动，每次移动的时候，把左指针当前指向的字符串的频率给相应的减掉。一直到发现右指针指向的字符串出现的频率是 0 次的时候，此时右指针就可以继续向右移动了。

追问

Follow-up：如果允许重复一次字符呢——微软-苏州-Lead面（2020.11.24）【来自 CodeTop 题目评论】

3. 无重复字符的最长子串 - 力扣（LeetCode）【仅供参考】

允许重复k个字符，字节-国际化电商-后端2022-4-22

base:3 follow up :395 424 2024

20230913 滴滴要求，滑动窗口检测不能用hashmap，真是弱智要求。

Peng：估计面试官是想让面试者使用数组，而不使用 HashMap。

20220213：

JD 后端二面 +打印最长子串

字节 变式题：给定一个字符串s，以及一个数字k，求s中最多不超过k个不同字符的最长子串长度【2022-11-27】

相关题目

LeetCode 395

395. 至少有 K 个重复字符的最长子串 - 力扣（LeetCode）

395. Longest Substring with At Least K Repeating Characters

340. 至多包含 K 个不同字符的最长子串 - 力扣（LeetCode）

[LeetCode] 340. Longest Substring with At Most K Distinct Characters 最多有K个不同字符的最长子串 - Grandyang - 博客园

LintCode 928：LintCode - LintCode