题目描述

题目链接

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

思路

我们先用一个例子考虑如何在较优的时间复杂度内通过本题。我们以字符串为例，找出从每一个字符开始的，不包含重复字符的最长子串，那么其中最长的那个字符串即为答案。对于示例字符串，我们列举出如下这些结果，其中括号中表示选中的字符以及最长的字符串：

• 以开始的最长字符串为
• 以开始的最长字符串为
• 以开始的最长字符串为
• 以开始的最长字符串为
• 以开始的最长字符串为
• 以开始的最长字符串为
• 以开始的最长字符串为
• 以开始的最长字符串为

发现了什么？如果我们依次递增地枚举子串的起始位置，那么子串的结束位置也是递增的！这里的原因在于，假设我们选择字符串中的第个字符作为起始位置，并且得到了不包含重复字符的最长子串的结束位置为。那么当我们选择第个字符作为起始位置时，首先从到的字符显然是不重复的，并且由于少了原本的第个字符，我们可以尝试继续增大，直到右侧出现了重复字符为止。

这样一来，我们就可以使用「滑动窗口」来解决这个问题了：

1. 我们使用两个指针表示字符串中的某个子串（或窗口）的左右边界，其中左指针代表着上文中「枚举子串的起始位置」，而右指针即为上文中的；
2. 在每一步的操作中，我们会将左指针向右移动一格，表示枚举下一个字符作为起始位置，然后我们可以不断地向右移动右指针，但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后，这个子串就对应着「以左指针开始的，不包含重复字符的最长子串」。记录下这个子串的长度；
3. 在枚举结束后，我们找到的最长的子串的长度即为答案。

判断重复字符
在上面的流程中，我们还需要使用一种数据结构来判断「是否有重复的字符」，常用的数据结构为哈希表。在左指针向右移动时，我们从哈希表中移除这个字符，在右指针向右移动时，我们往哈希表中添加一个字符。

代码实现

public int lengthOfLongestSubstring(String s) {
    Set<Character> set = new HashSet<>();
    int res = 0;
    // 右指针初始值为-1，相当于我们在字符串的左边界的左侧，还没有开始移动
    int rk = -1;
    for (int k = 0; k < s.length(); k++) {
        // 左指针向右移动一格，移除一个字符
        if (k != 0) {
            set.remove(s.charAt(k - 1));
        }
        // 右指针不断右移，直到出现重复字符
        while (rk + 1 < s.length() && !set.contains(s.charAt(rk + 1))) {
            set.add(s.charAt(rk + 1));
            rk++;
        }
        // 记录最长的无重复字符子串
        res = Math.max(res, rk - k + 1);
    }
    return res;
}

进阶实现：
上面的做法涉及哈希表频繁的插入删除操作，并且左指针和右指针会分别遍历整个字符串一次，实现较为啰嗦。实际上，我们可以用 HashMap 来保存字符及其下标位置，维护左右窗口的字符下标即可：

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> map = new HashMap<>();
    int res = 0;
    for (int k = 0, rk = 0; rk < s.length(); rk++) {
        char c = s.charAt(rk);
        if (map.containsKey(c)) {
            // 这里加一表示忽略第一个重复字符，即返回上一个重复字符的下一个位置
            k = Math.max(k, map.get(c) + 1);
        }
        res = Math.max(res, rk - k + 1);
        // 只需添加元素即可，因为重复字符会更新在map中的value值，value一直是最新下标
        map.put(c, rk);
    }
    return res;
}

针对第 8 行代码，为什么要和 k 做一次 max 比较呢？举个例子，如果当前字符 c 包含在 map 中的话，也就是第 6 行代码成立时，此时有两类情况：

1. 当前字符包含在当前有效的子串中，比如：abca，当我们遍历到第二个 a 时，当前有效最长子串是 abc，我们又遍历到 a，那么此时更新 k 为，当前有效子串更新后即为 bca；
2. 当前字符不包含在当前最长有效子串中，如：abba，我们先添加 a、b 到 map 中，此时 k=0，之后再添加 b 时，发现 map 中包含 b 并且 b 包含在最长有效子串中，我们更新，此时有效子串为 b。随后，我们遍历到 a，发现 a 也包含在 map 中，如果我们还像第一种情况一样直接加一的话，就会发现 ，实际上，k 此时应该不变，k 始终为 2，子串变成 ba 才对。

为了处理以上两类情况，于是我们每次更新。

复杂度分析

• 时间复杂度：，其中是字符串的长度，左指针和右指针分别会遍历整个字符串一次。
• 空间复杂度：，其中表示字符集（即字符串中可以出现的字符），表示字符集的大小。在本题中没有明确说明字符集，因此可以默认为所有 ASCII 码在 [0,128) 内的字符，即。我们需要用到哈希表来存储出现过的字符，而字符最多有个，因此空间复杂度为。