问题

3.无重复字符的最长子串

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

示例 1

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

练习

无重复字符的最长子串

# your python code

思路

北海啊，要多想！

提示

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

1. 定义两个指针构成窗口 使用两个指针维护一个滑动窗口，窗口内保证没有重复字符：l 表示窗口左边界，r 表示窗口右边界，不断向右扩展。
2. 滑动窗口拓展与收缩
   • 拓展：采用哈希表帮助判断 r 是否可以向右移动。
     • 哈希表中包含 s[r] ，向右移动。
     • 哈希表中不包含 s[r] ，停止移动。
   • 收缩：当右指针停止移动后，左指针向右移动，选择下一个字符作为枚举子串的起始位置。
3. 更新最大长度

Java

import java.util.HashSet;  
import java.util.Scanner;  
import java.util.Set;  
  
public class LC3LengthOfLongestSubstring {  
    public static void main(String[] args) {  
        // Scanner scanner = new Scanner(System.in);  
        // String s = scanner.nextLine();  
        // String s = "abcabcbb";
        String s = "bbbbb";  
  
        System.out.println(lengthOfLongestSubstring(s));  
    }  
    private static int lengthOfLongestSubstring(String s) {  
        int ans = 0, n = s.length();  
        Set<Character> occ = new HashSet<Character>();  
  
        int r = 0;  
        for (int l = 0; l < n; l++) {  
            while (r < n && !occ.contains(s.charAt(r))) {  
                occ.add(s.charAt(r));  
                r++;  
            }
            ans = Math.max(ans, r - l);  
            occ.remove(s.charAt(l));  
        }
        return ans;  
    }
}

复杂度分析：

• 时间复杂度：$\mathcal{O}(N)$。
• 空间复杂度：$\mathcal{O}(\lvert \Sigma \rvert)$。其中 $\Sigma$ 表示所有可能出现的字符集。