无重复字符的最长子串

## 题目

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

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

**示例 2:**

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

**示例 3:**

```txt
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
```

**示例 4:**

```txt
输入: s = ""
输出: 0
```

**提示：**

* 0 <= s.length <= 5 * 104
* s 由英文字母、数字、符号和空格组成

> 类似的题目还有：
>
> 1. [NC41 最长无重复子数组](https://www.nowcoder.com/practice/b56799ebfd684fb394bd315e89324fb4)。

## 问题解析

1. 定义一个窗口，窗口中的内容即为当前的不重复字串，其中窗口的左边界为 $left$，右边界为 $right$。
2. 定义一个 $Map$，里面存储每个元素的下标，用于判断元素是否存在。
3. 然后对元素进行遍历：
4. 当遍历一个元素在窗口中已经存在时，将 $left$ 的值更新为 $max(left, map.get(key))$，例如下图中 $left$ 的值为 2，当前遍历元素 $b$ 在 $map$ 中的值为 4，而 4 大于 2，因此将 $left$ 的值更新为 4。
   ![](https://notebook.ricear.com/media/202206/2022-06-10_160518_352603.png)
   ![](https://notebook.ricear.com/media/202206/2022-06-10_160533_448801.png)
5. 每遍历一个元素，$right$ 向右移动一位，同时计算当前不重复字串的最大长度 $max$，下图中 $right$ 与 $left$ 指针的距离为 2，$max$ 的值为 3，而 3 大于 2，因此此时 $max$ 的值不需要更新。
   ![](https://notebook.ricear.com/media/202206/2022-06-10_160726_616162.png)
6. 然后更新 $map$ 中元素的下标，将下图中当前遍历元素 $b$ 在 $map$ 中的值更新为当前滑动窗口右边界的下标，即更新为 6。
   ![](https://notebook.ricear.com/media/202206/2022-06-10_160754_123158.png)
7. 当所有元素遍历完后，$max$ 的值即为不重复字串的最大长度。
   ![](https://notebook.ricear.com/media/202206/2022-06-10_160841_797032.gif)

## 参考代码

```java
/**
 * 3. 无重复字符的最长子串（版本 1：滑动窗口）
 *
 * @param s 字符串
 * @return 无重复字符的最长子串
 */
public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> map = new HashMap<>();
    int left = 0, right = 0, res = 0;
    
    for (int i = 0; i < s.length(); i++) {
        char key = s.charAt(i);
        if (map.containsKey(key)) {
            left = Math.max(left, map.get(key));
            if (left == map.get(key)) {left++;}
        }
        map.put(key, i);
        res = Math.max(res, right-left+1);
        right++;
    }
    
    return res;
}
```

## 题目拓展

### 最多有 k 个不同字符的最长子字符串

> 题目来源：[386. 最多有 k 个不同字符的最长子字符串](https://www.lintcode.com/problem/386/description)。

#### 题目

**描述**
给定字符串*S*，找到最多有 k 个不同字符的最长子串*T*。**样例**
**样例 1:**

```
输入: S = "eceba" 并且 k = 3
输出: 4
解释: T = "eceb"
```

**样例 2:**

```
输入: S = "WORLD" 并且 k = 4
输出: 4
解释: T = "WORL" 或 "ORLD"
```

**挑战**
O(n) 时间复杂度

#### 问题解析

1. 本题同样可以采用 **滑动窗口** 的方法来解决。
2. 初始时滑动窗口的左右边界 $left$ 和 $right$ 均为 0，使用一个哈希表 $map$ 用于存储每个元素最近一次的下标。
3. 然后对字符串进行遍历：

> 假设当前遍历到的字符为 $key$。

1. 将当前遍历到的 **字符** 及其对应的 **下标** 存入到哈希表中，同时将滑动窗口的 **右边界** 右移。

> ```java
> map.put(key, right++);
> ```

2. 如果哈希表的大小超过 $k$，则：
3. 找到哈希表中 **最小的值** $minInd$。
4. 把其对应的 $key$ 从哈希表中删除。
5. 将滑动窗口的 **左边界** 更新为 $minInd + 1$。

> 需要注意的是此时左边界的值是更新为 $minInd + 1$，而不是直接右移。
>
> ```java
> minInd = Collections.min(map.values());
> map.remove(s.charAt(minInd));
> left++;
> ```

3. 更新最长子字符串的长度。

> ```java
> maxLen = Math.max(maxLen, right - left);
> ```

> 动画链接：[LTC386-最多有 k 个不同字符的最长子字符串](https://drive.google.com/file/d/18slDEH2RV9qRHXhs3Zy7GSodv_BsWv_g/view?usp=sharing)。

#### 参考代码

```java
/**
 * 386. 最多有k个不同字符的最长子字符串
 * @param s: 字符串
 * @param k: 不同字符的最大个数
 * @return: 最多有 k 个不同字符的最长字符串的长度
 */
public int lengthOfLongestSubstringKDistinct(String s, int k) {
    Map<Character, Integer> map = new HashMap<>();
    int left = 0, right = left, n = s.length(), maxLen = 0;

while (right < n) {
      char key = s.charAt(right);
      map.put(key, right++);

if (map.size() == k + 1) {
        int minInd = Collections.min(map.values());
        map.remove(s.charAt(minInd));
        left = minInd + 1;
      }

maxLen = Math.max(maxLen, right - left);
    }

return maxLen;
}
```

### 至少有 K 个重复字符的最长子串

> 题目来源：[395. 至少有 K 个重复字符的最长子串](https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters)。

#### 题目

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

**示例 1：**

~~~
输入：s = "aaabb", k = 3
输出：3
解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。
~~~

**示例 2：**

~~~
输入：s = "ababbc", k = 2
输出：5
解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。
~~~

**提示：**

- 1 <= s.length <= 104
- s 仅由小写英文字母组成
- 1 <= k <= 105

#### 问题解析

1. 解答本题的核心思想是 **如果一个字符在原来字符串中出现的次数小于 $k$**，**则包含这个字符的所有字符串都是不符合要求的**。

2. 根据以上思想，我们可以按照如下的思路来解决：

1. 使用哈希表记录**所有字符在原来字符串中出现的次数**。

> ~~~java
      > Map<Character, Integer> map = new HashMap<>();
      > for (char key: map.keySet()) {
      > map.put(key, map.getOrDefault(key, 0) + 1);
      > }
      > ~~~

> $map$ 的长度最大为 **26**。

2. 遍历原来的字符串，如果当前遍历到的字符 $key$ **在原来字符串中出现的次数小于** $k$，则将原来的字符串根据 $key$ 进行 **切分**，至少有 $k$ 个重复的最长子串肯定在这些切分后的字符串中，因此在切分后的子串中 **递归** 寻找至少有 $k$ 个重复的最长子串，并在符合条件的字串中取 **最大值**。

![image-20220728122903761](https://notebook.ricear.com/media/202207/2022-07-28_122915_1208940.07726193607571075.png)

> ~~~java
      > int res = 0;
      > for (int i = 0; i < s.length(); i++) {
      > char key = s.charAt(i);
      > if (map.get(key) < k) {
      >  String[] splits = s.split(String.valueOf(key));
      >  for (String t: splits) {
      >    res = Math.max(res, longestSubstring(t, k));
      >  }
      > }
      > }
      > ~~~

3. 如果原来的字符串中 **所有的字符出现的次数都大于等于** $k$，则直接返回 **原来的字符串的长度**。

#### 参考代码

~~~java
/**
 * 395. 至少有 K 个重复字符的最长子串
 * 
 * @param s 字符串
 * @param k 重复字符的最小值
 */
public int longestSubstring(String s, int k) {
    Map<Character, Integer> map = new HashMap<>();
    int res = 0;
    
    for (char key: s.toCharArray()) {
        map.put(key, map.getOrDefault(key, 0) + 1);
    }
    
    for (char key: s.toCharArray()) {
        if (map.get(key) < k) {
            String[] splits = s.split(String.valueOf(key));
            for (String t: splits) {
                res = Math.max(res, longestSubstring(t, k));
            }
            return res;
        }
    }
    
    return s.length();
}
~~~

## 参考文献

1. [无重复字符的最长子串『官方题解』](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetc-2)。
2. [滑动窗口](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-dong-chuang-kou-by-powcai)。
3. [方法：滑动窗口 + 哈希表](https://www.lintcode.com/problem/386/solution/57157)。
4. [借本题帮助大家理解递归](https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/solution/jie-ben-ti-bang-zhu-da-jia-li-jie-di-gui-obla)。