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

题目描述

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

注意： 子串是连续的字符序列。

示例 1

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

示例 2

• 输入： s = "bbbbb"
• 输出： 1
• 解释： 无重复字符的最长子串是 "b"，其长度为 1。

示例 3

• 输入： s = "pwwkew"
• 输出： 3
• 解释： 无重复字符的最长子串是 "wke"，其长度为 3。
  说明： 答案必须是子串的长度，"pwke" 虽然是一个子序列，但不是子串。

---

解题思路

利用滑动窗口思想解决此题：

1. 窗口定义：
   使用两个指针 start 和 end 定义窗口的左右边界，初始时都指向字符串的开始位置。
2. 状态维护：
   使用一个字典（或哈希表） char_index 记录每个字符上一次出现的位置。
3. 窗口滑动：
   遍历字符串：
   • 如果当前字符 s[end] 在 char_index 中出现过且其索引不小于 start，说明该字符在当前窗口内重复。此时，将 start 更新为 char_index[s[end]] + 1，以缩小窗口，确保窗口内字符不重复。
   • 更新 char_index[s[end]] 为当前的索引 end。
   • 每一步都计算当前窗口的长度 end - start + 1，并更新最大值。
4. 时间复杂度：
   该算法只遍历一次字符串，时间复杂度为 O(n)。

---

Python 实现

def length_of_longest_substring(s: str) -> int:
    char_index = {}  # 记录字符最后出现的位置
    longest = 0
    start = 0  # 窗口起始位置
    for end, char in enumerate(s):
        if char in char_index and char_index[char] >= start:
            # 出现重复字符，移动窗口起始位置
            start = char_index[char] + 1
        char_index[char] = end
        longest = max(longest, end - start + 1)
    return longest

# 测试用例
if __name__ == "__main__":
    test_cases = [
        ("abcabcbb", 3),
        ("bbbbb", 1),
        ("pwwkew", 3),
        ("", 0),
        ("au", 2)
    ]
  
    for s, expected in test_cases:
        result = length_of_longest_substring(s)
        print(f"输入: \"{s}\", 预期: {expected}, 得到: {result}")

代码疑问

 last_index = char_index.get(char, -1)

是 Python 字典的 get() 方法，它的作用是：

• 如果 char 在 char_index 这个字典里，就返回 char 对应的值（即字符的上次索引）。
• 如果 char 不在字典里，就返回 -1（默认值 -1 是 get() 方法的第二个参数）

1. char_index 是空字典，get() 不会报错？

不会报错！

因为 get() 方法即使在字典里找不到 char，它也不会抛出错误，而是返回 -1（或者你设置的默认值）。

示例：

 char_index = {}  # 空字典
 print(char_index.get('a', -1))  # 不会报错，返回 -1
 

相比于 char_index[char]（如果 char 不在字典里会报错 KeyError），get() 更安全。

2. -1 是什么意思？

-1 代表字符 还没有出现过。

• 在 char_index 字典里，存的是字符的最新索引，但如果 char 还没出现，就找不到索引。
• 我们用 -1 作为默认值，表示“这个字符从未出现”。

例子：

 s = "abcabcbb"
 char_index = {}  # 存字符的索引
 for i, char in enumerate(s):
     last_index = char_index.get(char, -1)  # 获取字符的上次索引，默认值是 -1
     print(f"字符: {char}, 之前索引: {last_index}")
     char_index[char] = i  # 更新最新索引
 

输出

 字符: a, 之前索引: -1
 字符: b, 之前索引: -1
 字符: c, 之前索引: -1
 字符: a, 之前索引: 0
 字符: b, 之前索引: 1
 字符: c, 之前索引: 2
 字符: b, 之前索引: 4
 字符: b, 之前索引: 6
 

a、b、c 第一次出现时，last_index 是 -1。

后续 a 再次出现时，它的 last_index 就是 0（上一次出现的位置）。

3. 为什么要用 -1 而不是 None？

• -1 这个数值可以直接进行数值比较（>= start），代码更简洁。
• 不能直接比较，会报错：

 if None >= 0:  # TypeError
     print("错误")

4. get() vs dict[key]

方法	键存在	键不存在	是否报错
dict[key]	✅ 返回值	❌KeyError	会报错
dict.get(key)	✅ 返回值	✅ 返回 None	不会报错
dict.get(key, 默认值)	✅ 返回值	✅ 返回 默认值	不会报错

---

Java 实现

import java.util.HashMap;
import java.util.Map;

public class LongestSubstringWithoutRepeating {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> charIndex = new HashMap<>();
        int longest = 0;
        int start = 0;  // 窗口起始位置
  
        for (int end = 0; end < s.length(); end++) {
            char ch = s.charAt(end);
            if (charIndex.containsKey(ch) && charIndex.get(ch) >= start) {
                // 遇到重复字符，更新窗口起始位置
                start = charIndex.get(ch) + 1;
            }
            charIndex.put(ch, end);
            longest = Math.max(longest, end - start + 1);
        }
        return longest;
    }

    public static void main(String[] args) {
        LongestSubstringWithoutRepeating solver = new LongestSubstringWithoutRepeating();
        String[] testCases = {"abcabcbb", "bbbbb", "pwwkew", "", "au"};
        int[] expectedResults = {3, 1, 3, 0, 2};

        for (int i = 0; i < testCases.length; i++) {
            int result = solver.lengthOfLongestSubstring(testCases[i]);
            System.out.println("输入: \"" + testCases[i] + "\", 预期: " + expectedResults[i] + ", 得到: " + result);
        }
    }
}

题目二：至多包含 K 个不同字符的最长子串

题目描述

给定一个字符串 s 和一个整数 k，请你找出其中包含最多 k 个不同字符的最长子串，并返回该子串的长度。

示例 1：

• 输入： s = "eceba", k = 2
• 输出： 3
• 解释： 最长子串为 "ece"，长度为 3。

示例 2：

• 输入： s = "aa", k = 1
• 输出： 2
• 解释： 整个字符串 "aa" 满足条件，长度为 2。

---

解题思路

1. 定义滑动窗口：
   使用两个指针 left 和 right 定义窗口的左右边界，初始时均指向字符串开头。
2. 维护窗口状态：
   使用一个字典 char_freq 记录窗口内各字符出现的次数，从而知道窗口中不同字符的个数。
3. 扩展窗口：
   不断将 right 指针向右移动，将新字符加入窗口，并更新其频率。
4. 收缩窗口：
   当窗口内不同字符的个数超过 k 时，移动 left 指针缩小窗口，直至窗口内不同字符数不超过 k。
5. 更新答案：
   在每个窗口状态下，更新当前最长子串的长度。

---

Python 实现

def length_of_longest_substring_k_distinct(s: str, k: int) -> int:
    if k == 0:
        return 0  # 如果 k 为 0，则任何字符都不允许出现

    char_freq = {}  # 记录当前窗口内各字符的出现频率
    max_length = 0
    left = 0  # 窗口左边界

    for right, char in enumerate(s):
        # 将当前字符加入窗口，更新频率
        char_freq[char] = char_freq.get(char, 0) + 1

        # 当窗口内不同字符数超过 k 时，收缩窗口
        while len(char_freq) > k:
            # 移除窗口最左侧的字符
            char_freq[s[left]] -= 1
            if char_freq[s[left]] == 0:
                del char_freq[s[left]]
            left += 1

        # 更新当前最长子串长度
        max_length = max(max_length, right - left + 1)

    return max_length

# 测试用例
if __name__ == "__main__":
    test_cases = [
        {"s": "eceba", "k": 2, "expected": 3},
        {"s": "aa", "k": 1, "expected": 2},
        {"s": "a", "k": 0, "expected": 0},
        {"s": "abaccc", "k": 2, "expected": 4}  # "accc" 或 "bacc" 均满足条件，长度为4
    ]
  
    for case in test_cases:
        result = length_of_longest_substring_k_distinct(case["s"], case["k"])
        print(f"输入: s = \"{case['s']}\", k = {case['k']} -> 预期: {case['expected']}, 得到: {result}")

---

说明

• 滑动窗口思想：
  通过维护一个不断扩展或收缩的窗口，保证窗口内的不同字符数不超过 k，从而高效计算满足条件的子串长度。
• 时间复杂度：
  该算法仅需遍历字符串一次，时间复杂度为 O(n)。
• 字典的使用：
  Python 中的 dict 就是基于哈希表实现的，用来快速记录和更新字符频率。