# 0003. Longest Substring Without Repeating Characters
###### tags: `Leetcode` `Medium` `Sliding Window`
Link: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
## 思路
### 方法一 Sliding Window
如果我们依次递增地枚举子串的起始位置，那么子串的结束位置也是递增的！所以可以使用「滑动窗口」来解决这个问题了
用map记录当前字符最近出现过的位置，如果不在window里面，that's fine, 如果在的话，就要把left挪到最近出现过的位置+1

### 方法二 动态规划
* 状态定义： 设动态规划列表 $dp$ ，$dp[j]$ 代表以字符 $s[j]$ 为结尾的 “最长不重复子字符串” 的长度。
* 转移方程： 固定右边界 $j$ ，设字符 $s[j]$ 左边距离最近的相同字符为 $s[i]$ ，即 $s[i] = s[j]$ 。
- 当 $i < 0$ ，即 $s[j]$ 左边无相同字符，则 $dp[j] = dp[j-1] + 1$ ；
- 当 $dp[j - 1] < j - i$ ，说明字符 $s[i]$ 在子字符串 $dp[j−1]$ 区间之外 ，则 $dp[j] = dp[j - 1] + 1$ ；
- 当 $dp[j - 1] \geq j - i$ ，说明字符 $s[i]$ 在子字符串 $dp[j-1]$ 区间之中 ，则 $dp[j]$ 的左边界由 $s[i]$ 决定，即 $dp[j] = j - i$ ；

\begin{equation}
dp[j] =
\left\{
\begin{array}{rcl}
dp[j-1]+1,& & {dp[j-1]<j-i}\\
j-i, & & {dp[j-1]\geq j-i}\\
\end{array} \right.
\end{equation}

### 方法三 用map记录之前出现过的所有字符及最后出现的位置
后来做题的时候想到的方法
如题，遍历字符串，并用map记录之前出现过的所有字符及最后出现的位置
接着分两种情况
* 如果一个字符s[i]出现过，也就是map.contains = true那么就更新他的value值，并且length也要减掉s[i]-map.get(s[i])(上次出现过的位置)，start（新的不重复字符串的起始点）也要改成i，但注意如果map.get(s[i])已经小于start了，例如s = "tmmzuxt"，遇到第二个t时的状况，则不需要更新length
* 如果没出现过，则length++，并跟maxLength比较看是否需要更新

## Code
### 方法一

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int l=0, r=0, ans=0;
        while(r<s.length()){
            char c = s.charAt(r);
            if(map.containsKey(c) && map.get(c)>=l){
                ans=Math.max(ans, r-l);
                l=map.get(c)+1;
            }
            map.put(c,r);
            r++;
        }
        ans = Math.max(ans, r-l);
        return ans;
    }
}

### 方法三

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int res = 0, tmp = 0;
        for(int j = 0; j < s.length(); j++) {
            int i = dic.getOrDefault(s.charAt(j), -1); // 获取索引 i
            dic.put(s.charAt(j), j); // 更新哈希表
            tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j]
            res = Math.max(res, tmp); // max(dp[j - 1], dp[j])
        }
        return res;
    }
}

### 方法四

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == "") return 0;
        int maxLength = 0;
        int length = 0;
        int start = 0;
        HashMap<Character,Integer> hashMap = new HashMap<>();
        for(int i = 0;i < s.length();i++){
            char currChar = s.charAt(i);
            if(hashMap.containsKey(currChar)){
                if(hashMap.get(currChar)<start){
                    hashMap.put(s.charAt(i),i);
                    length++;
                }
                else {
                    if (length > maxLength) {
                        maxLength = length;
                    }
                    length -= hashMap.get(currChar) - start;
                    start = hashMap.get(currChar) + 1;
                    hashMap.put(s.charAt(i), i);
                }
            }
            else{
                hashMap.put(s.charAt(i),i);
                length++;
            }
            if(length > maxLength){
                maxLength = length;
            }
        }
        return maxLength;
    }
}