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

# 1. 题目详情

📗difficulty：Medium

🎯Tags：

题目描述：

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

样例1：

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

1
2
3

样例2：

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

1
2
3

# 2. 解题思路

Version 1： HashSet 判重

public static int lengthOfLongestSubstring(String s) {
    int maxsublen = 0;
    int front, back; // 不需要初始化
    HashSet<Character> hashSet = new HashSet<>();
    for (front = 0; front < s.length(); front++) {
        hashSet.clear();
        for (back = front; back < s.length(); back++) {
            if (hashSet.contains(s.charAt(back))) {
                break;
            } else {
                hashSet.add(s.charAt(back));
            }
        }
        maxsublen = Math.max(back - front, maxsublen);
    }
    return maxsublen;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

设置 2 个指针，一个指针指示当前子串的头部，一个指针指示当前子串的尾部，每次该子串的尾部是否包含相同的字符进行判断，利用 HashSet 中元素不重复的性质。遇到重复的元素，则进行判断，当前子串的长度是否是最长的，每次对这个 maxsublen 的值进行更新。

# 3. 优秀解答

采取 leetcode-cn 官方的题解思路。

# 3.1 暴力法

📃帖子原址 (opens new window)

暴力法本身不值得考量，多重循环注定是不能接受的时间开销。但是作为算法复杂度的分析样例，是个很好的例子。

核心代码：

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;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

首先使用双重循环，列举可能出现的全部结果，再对每次组合产生的子串，进行检查，如果不包含重复的字符，那么和当前的最长子串长度进行比较，更新最长子串的长度。

# 3.2 滑动窗口

📃帖子原址 (opens new window)

以下分析为 leetcode-cn 官方提供

核心代码：

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;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

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

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

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

滑动窗口是数组/字符串问题中常用的抽象概念。窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即 $[i, j)$ （左闭，右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如，我们将 $[i, j)$ 向右滑动 1 个元素，则它将变为 $[i+1, j+1)$ （左闭，右开）。

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

Complexity analysis:

Time complexity : $O(2n)=O(n)$ ，在最糟糕的情况下，每个字符将被 $i$ 和 $j$ 访问两次。
Space complexity: $O(min(m,n))$ ，与之前的方法相同。滑动窗口法需要 $O(k)$ 的空间，其中 $k$ 表示 Set 的大小。而 Set 的大小取决于字符串 $n$ 的大小以及字符集 / 字母 $m$ 的大小。

# 3.3 优化的滑动窗口

📃帖子原址 (opens new window)

以下分析为 leetcode-cn 官方提供

核心代码：

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>(); // current index of character
        // try to extend the range [i, j]
        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;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

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

# 如果假定字符集是 ASCII

以前的我们都没有对字符串 s 所使用的字符集进行假设。

当我们知道该字符集比较小的时候，我们可以用一个整数数组作为直接访问表来替换 Map。

常用的表如下所示：

int [26] 用于字母 ‘a’ - ‘z’ 或 ‘A’ - ‘Z’
int [128] 用于ASCII码
int [256] 用于扩展ASCII码

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        int[] index = new int[128]; // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            i = Math.max(index[s.charAt(j)], i);
            ans = Math.max(ans, j - i + 1);
            index[s.charAt(j)] = j + 1;
        }
        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

复杂度分析：

时间复杂度： $O(n)$ ，索引 $j$ 将会迭代 $n$ 次。
空间复杂度（HashMap）： $O(min(m, n))$ ，与之前的方法相同。
空间复杂度（Table）： $O(m)$ ， $m$ 是字符集的大小。

← 2.两数之和链表版 14.最长公共前缀 →