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

题目：无重复字符的最长子串

描述：

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

---

示例：

示例 1:

输入: s = "abcabcbb"
输出: 3
解释: 最长子串是 "abc"，其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 最长子串是 "b"，其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 最长子串是 "wke"，其长度为 3。
注意: 答案必须是子串，"pwke" 是子序列，不是子串。

示例 4:

输入: s = ""
输出: 0

---

解题思路：

我们可以用 滑动窗口法 高效地解决这个问题。滑动窗口可以动态地维护一个窗口范围，用来检查是否有重复字符，并在发现重复时调整窗口。

---

滑动窗口法步骤：

1. 初始化窗口边界和数据结构：

   • 使用两个指针 left 和 right 分别表示窗口的左右边界，初始值为 0。
   • 使用一个哈希表 set（或其他类似数据结构）存储窗口内的字符，用于快速判断字符是否重复。

2. 滑动窗口：

   • 每次将窗口右边界 right 向右扩展一个字符。
   • 如果 right 指向的字符未在窗口中（即未出现在 set 中），则将其加入窗口，并更新最大长度。
   • 如果 right 指向的字符已在窗口中，表示发生了重复：
     • 移动左边界 left，逐步将重复字符移出窗口，直到窗口内不再有重复字符。

3. 更新最大长度：

   • 每次调整窗口时，检查窗口大小并更新最长子串的长度。

4. 终止条件：

   • 当右指针遍历完整个字符串时，返回最长子串的长度。

---

代码实现：

import java.util.Scanner;
import java.util.HashSet;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Read input string
        String s = scanner.nextLine();

        Solution solution = new Solution();
        int result = solution.lengthOfLongestSubstring(s);

        System.out.println(result);
        scanner.close();
    }
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 使用滑动窗口
        HashSet<Character> set = new HashSet<>();
        int left = 0; // 左指针
        int maxLength = 0;

        // 遍历字符串，右指针移动
        for (int right = 0; right < s.length(); right++) {
            char currentChar = s.charAt(right);

            // 如果字符已经存在于窗口中，则移动左指针缩小窗口
            while (set.contains(currentChar)) {
                set.remove(s.charAt(left));
                left++;
            }

            // 添加当前字符到窗口，并更新最大长度
            set.add(currentChar);
            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }
}

---

时间复杂度分析：

1. 时间复杂度：

   • 每个字符最多被访问两次（一次被右指针访问，一次被左指针移出），因此时间复杂度为 O(n)，其中 n 是字符串长度。

2. 空间复杂度：

   • 使用了一个哈希集合存储当前窗口中的字符，空间复杂度为 O(k)，其中 k 是字符集大小（对于字母和数字，k 通常是固定的 26 或 128）。

---

总结：

• 滑动窗口法是一种高效的方法，能够在线性时间内解决字符串子串问题。
• 通过动态调整窗口的左右边界，可以有效避免重复字符，同时保证计算子串长度时的准确性。