C#算法之无重复字符的最长子串

问题描述

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

示例 1:

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

示例 2:

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

解决思路

暴力法

对于每一个字符从它开始依次枚举所有可能的子串，检查每个子串是否含有重复字符。

复杂度分析：
- 时间复杂度：O(n^3)，枚举所有子串需要 O(n^2)，检查每个子串是否含有重复字符需 O(n)。
- 空间复杂度：O(min(n,m))，n 是字符串长度，m 是字符集大小。

滑动窗口法

使用哈希表来判重，定义两个指针 i 和 j 分别代表窗口的左右边界。从左边界开始，逐一向右尝试扩大窗口大小，每次判断右侧添加的字符是否已经在窗口内出现过，如果已经出现过则缩小窗口，即左边界右移，同时左侧字符从哈希表中移除。

复杂度分析：
- 时间复杂度：O(n)，窗口大小从1向右依次遍历，每个字符最多被访问两次，一次是右边界扫描，一次是左边界扫描。
- 空间复杂度：O(min(n,m))，右边界不断向右扩张，因此只需要在哈希表中存储字符的最后出现位置即可，而由于最多有m个不同字符，因此空间复杂度为O(min(n,m))。

代码实现

暴力法代码

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

private bool AllUnique(string s, int start, int end) {
    HashSet<char> set = new HashSet<char>();
    for (int i = start; i < end; i++) {
        char c = s[i];
        if (set.Contains(c)) return false;
        set.Add(c);
    }
    return true;
}

滑动窗口法代码

public int LengthOfLongestSubstring(string s) {
    int n = s.Length, ans = 0;
    Dictionary<char, int> dict = new Dictionary<char, int>();
    for (int i = 0, j = 0; j < n; j++) {
        if (dict.ContainsKey(s[j])) i = Math.Max(dict[s[j]], i);
        ans = Math.Max(ans, j - i + 1);
        dict[s[j]] = j + 1;
    }
    return ans;
}

示例说明

示例一

输入: "abcabcbb"
输出: 3

暴力法的思路：逐一枚举所有子串，检查每个子串是否含有重复字符。

• 子串"a"没有重复字符。
• 子串"ab"没有重复字符。
• 子串"abc"没有重复字符。
• 子串"abca"有重复字符"a"，因此子串"abca"被排除。
• 子串"b"没有重复字符。
• 子串"bc"没有重复字符。
• 子串"bca"有重复字符"c"，因此子串"bca"被排除。
• 子串"bcab"有重复字符"b"，因此子串"bcab"被排除。
• 子串"c"没有重复字符。
• 子串"cb"有重复字符"b"，因此子串"cb"被排除。
• 子串"cbb"有重复字符"b"，因此子串"cbb"被排除。
• 子串"cbba"有重复字符"b"和"a"，因此子串"cbba"被排除。

因此，无重复字符的最长子串是"abc"，长度为3。

滑动窗口法的思路：定义两个指针i和j分别代表窗口的左右边界，使用哈希表来判重。从左边界开始，逐一向右尝试扩大窗口大小，每次判断右侧添加的字符是否已经在窗口内出现过，如果已经出现过则缩小窗口，即左边界右移，同时左侧字符从哈希表中移除。

• 首先，i=0,j=0已经覆盖了第一个字符"a"。
• 向右移动右指针，j=1，发现字符"b"未曾出现，此时窗口大小为2。
• 向右移动右指针，j=2，发现字符"c"未曾出现，此时窗口大小为3。
• 向右移动右指针，j=3，发现字符"a"曾经在(i,j)范围内出现过，于是将左指针右移，此时i=1，窗口大小为2。
• 向右移动右指针，j=4，发现字符"b"曾经在(i,j)范围内出现过，于是将左指针右移，此时i=2，窗口大小为2。
• 向右移动右指针，j=5，发现字符"c"曾经在(i,j)范围内出现过，于是将左指针右移，此时i=3，窗口大小为2。
• 向右移动右指针，j=6，发现字符"b"曾经在(i,j)范围内出现过，于是将左指针右移，此时i=4，窗口大小为2。

因此，无重复字符的最长子串是"abc"，长度为3。

示例二

输入: "bbbbb"
输出: 1

暴力法的思路：逐一枚举所有子串，检查每个子串是否含有重复字符。

• 子串"b"没有重复字符。
• 子串"bb"有重复字符"b"，因此子串"bb"被排除。
• 子串"bbb"有重复字符"b"，因此子串"bbb"被排除。
• 子串"bbbb"有重复字符"b"，因此子串"bbbb"被排除。

因此，无重复字符的最长子串是"b"，长度为1。

滑动窗口法的思路：定义两个指针i和j分别代表窗口的左右边界，使用哈希表来判重。从左边界开始，逐一向右尝试扩大窗口大小，每次判断右侧添加的字符是否已经在窗口内出现过，如果已经出现过则缩小窗口，即左边界右移，同时左侧字符从哈希表中移除。

• 首先，i=0,j=0已经覆盖了第一个字符"b"。
• 向右移动右指针，j=1，发现字符"b"曾经在(i,j)范围内出现过，于是将左指针右移，此时i=1，窗口大小为1。
• 向右移动右指针，j=2，发现字符"b"曾经在(i,j)范围内出现过，于是将左指针右移，此时i=2，窗口大小为1。
• 向右移动右指针，j=3，发现字符"b"曾经在(i,j)范围内出现过，于是将左指针右移，此时i=3，窗口大小为1。
• 向右移动右指针，j=4，发现字符"b"曾经在(i,j)范围内出现过，于是将左指针右移，此时i=4，窗口大小为1。

因此，无重复字符的最长子串是"b"，长度为1。