LeetCode/solutions/3. Longest Substring Without Repeating Characters.md

# [3. Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/)
# 思路
## 思路一、暴力动归
用一个与s等长数组dp记录以某个字符结尾的最长不重复子串的长度，即`dp[i] = m`表示以s[i]结尾的最长不重复子串的长度为m。所以dp初始化全为1.    
dp[i]应该这样计算：   
* 从s[i-1]开始往前遍历dp[i-1]个字符，若中途遍历到某个字符与s[i]相等了则跳出循环。若往前遍历了tmp(从0开始)个字符，则`dp[i] = 1 + tmp`。    

由于计算dp[i]时只用到了前一个dp[i-1]，所以可采用滚动数组的方式将空间优化至O(1)

时间复杂度O(n*n)，空间复杂度O(1)

## 思路二、窗口法
用一个hash map(这里直接用一个长为128数组就行了，因为ASCII就是0-127) mp记录某个字符c在s中的位置，初始全-1.    
用left、right记录当前窗口左、右边的位置，窗口[left ~ right]中保证是无重复的。    

left和right初始都为0，right从0开始不断加1并按下面步骤循环:  
* 设当前字符为c，
    1. 若 `mp[c] >= left`，则字符c第二次出现在了窗口中，将left更新到上一个c所在位置的下一个位置; 
    2. 还要更新` mp[c] = right`以及res。

由于两个指针从左到右都只遍历了一次，所以时间复杂度O(n)，空间复杂度O(1)

值得一提的是，mp的作用就是记录 c 是否已经在窗口内，所以也可以用一个set，把出现过的字符都放入其中，如果遇到重复的，则从左边开始删字符，直到删到重复的字符。

# C++
## 思路一
``` C++
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.empty()) return 0;
        int dp = 1, res = 1, tmp;
        for(int i = 1; i < s.size(); i++){
            for(tmp = 0; tmp < dp; tmp++) // 往前遍历dp[i - 1]个字符
                if(s[i] == s[i - 1 - tmp]) break;
        
            dp = 1 + tmp;
            res = max(res, dp);
        }
        return res;
    }
};
```
## 思路二
``` C++
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int>mp(128, -1); // 记录s中某个字符所在位置，初始为-1
        
        int left = 0, right = 0, res = 0; // 窗口[left~right]中保证是无重复的
        char c;
        for(; right < s.size(); right++){
            c = s[right];
            if(mp[c] >= left) // 字符c第二次出现在了窗口中, 更新left
                left = mp[c] + 1; // 更新到上一个c所在位置的下一个位置
    
            mp[c] = right;
            res = max(res, right - left + 1);
        }
        return res;
    }
};
```