3. Longest Substring Without Repeating Characters.md

3. 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++

思路一

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;
    }
};

思路二

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;
    }
};