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

要找出给定字符串中不含重复字符的最长子串的长度，可以使用滑动窗口（Sliding Window）技术。这种方法可以高效地解决问题，时间复杂度为 O(n)，其中 n 是字符串的长度。

1. 解题思路

• 滑动窗口：使用两个指针（start 和 end）来维护一个滑动窗口，其中窗口内的子串不包含重复字符。
• 哈希表（Set）：使用一个哈希表（Set）来存储当前窗口内的字符。
• 扩展窗口：逐步移动右指针 end，每次移动时检查字符是否已经在窗口内（即在 Set 中）。
• 收缩窗口：如果发现重复字符，则移动左指针 start，从窗口中移除字符，直到不再有重复字符。
• 更新结果：在过程中，持续更新不含重复字符的最长子串的长度。

2. 代码实现

import java.util.HashSet;
import java.util.Set;

public class LongestSubstringWithoutRepeatingCharacters {

    public static int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int maxLength = 0;
        int start = 0; // 左指针
        Set<Character> set = new HashSet<>(); // 用来存储当前窗口内的字符

        for (int end = 0; end < n; end++) { // 右指针
            char currentChar = s.charAt(end);

            // 如果当前字符已在窗口内，移动左指针直到窗口内没有重复字符
            while (set.contains(currentChar)) {
                set.remove(s.charAt(start));
                start++;
            }

            // 将当前字符加入窗口
            set.add(currentChar);

            // 更新最长子串的长度
            maxLength = Math.max(maxLength, end - start + 1);
        }

        return maxLength;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println("Length of the longest substring without repeating characters: " + lengthOfLongestSubstring(s));
    }
}

3. 示例解释

假设输入字符串为 "abcabcbb"，按照上述算法执行的过程如下：

1. 初始化 start = 0, end = 0, maxLength = 0，Set 为空。
2. 右指针 end 逐步向右移动，窗口变为 "a", "ab", "abc"，此时没有重复字符，maxLength 更新为 3。
3. 当 end 指针到达第 4 个字符时（s[3] = 'a'），发现 a 已经在 Set 中，因此移动左指针 start，将 a 从 Set 中移除，并继续处理。
4. 重复此过程，最终计算出最长子串为 "abc" 或 "bca" 或 "cab"，长度为 3。

4. 复杂度分析

• 时间复杂度：O(n)，因为每个字符在滑动窗口内最多被插入和移除一次。
• 空间复杂度：O(min(n, m))，其中 n 是字符串的长度，m 是字符集的大小（对 ASCII 字符集，m 最多为 128）。

5. 总结

通过滑动窗口技术，可以有效地找到字符串中不含重复字符的最长子串的长度。该算法的关键在于使用两个指针动态调整窗口大小，以及哈希表（Set）来维护窗口内的字符集合。