# 3. 无重复字符最长字串

## 题目

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

示例 1:

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

示例 2:

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

 示例 3:

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

## 思路1 暴力解

逐个检查所有的子字符串，看它是否不含有重复的字符。

## 思路2 滑动窗口

在暴力法中，我们会反复检查一个子字符串是否含有有重复的字符，但这是没有必要的。

{% hint style="info" %}
滑动窗口是数组/字符串问题中常用的抽象概念。 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即 \[i, j)\[i,j)（左闭，右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如，我们将 \[i, j)\[i,j) 向右滑动 11 个元素，则它将变为 \[i+1, j+1)\[i+1,j+1)（左闭，右开）
{% endhint %}

滑动窗口的解法是：

1. 设置内外两层循环i , j ; i为外层循环，j为内层循环, 使用数组win来存储\[i, j)的数字
2. 如果s\[j]值存在于\[i,j), 那么下次设置 i = i + 1
3. 如果s\[j]值不存在与\[i,j), 那么设置 j = j + 1
4. 最后统计最大的win长度

## 思路3 优化滑动窗口

在思路2的基础上，让s\[j]值存在与\[i,j)中时，把i直接跳到\[i,j)中s\[j]值索引的下一位

### JavaScript实现

```javascript
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    const infoMap = new Map();
    let i = j = maxSub = 0;
    for(let i = j = 0; j < s.length; j++){
        if(infoMap.has(s.charAt(j))){
            i = Math.max(infoMap.get(s.charAt(j)), i);
        }
        maxSub = Math.max(maxSub, j-i+1);
        infoMap.set(s.charAt(j), j+1);
    }
    return maxSub;
};
```