题目描述

给定一个字符串，请找出最长的不包含重复字符的子串。
请注意子串和子序列的区别：

子串一定是连续的一段
子序列不一定是连续的一段，但下标要求是递增的

样例

给定 "abcabcbb"，答案是"abc"，长度是3.
给定 "bbbbb"，答案是"b"，长度是1.
给定 "pwwkew"，答案是"wke"，长度是3.

算法1

(暴力枚举) $O(n^3)$

两重循环枚举所有substring。对于每个substring再用一重循环判断是否unique。总时间复杂度是 $O(n^3)$ 。

时间复杂度分析： $O(n^3)$

C++ 代码

// brute force 
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int maxLen = 0;
        if(!s.size())
            return maxLen;
        for(int i = 0; i < s.size(); i++){
            for(int j = 0; j < s.size(); j++){
                if(isUniq(s, i, j))
                    maxLen = max(maxLen, j-i+1);
            }
        }
        return maxLen;
    }
    bool isUniq(string s, int start, int end){
        set<char> uniqSet;
        for(int i = start; i <= end; i++){
            if(uniqSet.count(s[i]))
                return false;
            uniqSet.insert(s[i]);
        }
        return true;
    }
};

算法2

(slide window with set or hashmap) $O(2n)$

yxc的方法好像属于这一类。hashmap或set里保存该双指针中间的substring的char frequency。右端指针每前进一位要到hashmap/set里判断是否出现过。如果出现，左端指针前进一位并更新hashmap/set，直到右端指针指向的char被删掉为止，然后更新maxLen。

用set还是hashmap个人觉得完全没区别。

时间复杂度分析：最坏情况每个char被左右指针分别访问一次（全重复序列）。遍历了2n个状态，所以复杂度$O(2n)$。（为了和下面的区分）

C++ 代码

// slide window with set
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int maxLen = 0;
        set<char> uniqSet;
        if(!s.length()) 
            return maxLen;
        int n = s.length();
        int i = 0, j = 0;
        while(i<n && j<n){
            if(!uniqSet.count(s[j])){
                uniqSet.insert(s[j]);
                maxLen = max(maxLen, j-i+1);
                j++;
            }
            else{

                uniqSet.erase(s[i]);
                i++;

            }
        }
        return maxLen;
    }
};

// slide window with hashmap
class Solution {
public:
    int ans = 0;
    int lengthOfLongestSubstring(string s) {
        unordered_map<char ,int> hash;
        if(s == "") return ans;
        for(int i = 0, j = 0; j < s.size(); j++){
            if(++hash[s[j]] > 1){
                while(i < j){
                    hash[s[i]]--;
                    i++;
                    if(hash[s[j]] == 1){
                        break;
                    } 
                }
            }
        ans = max(ans, j-i+1);
        }
        return ans;
    }
};

算法3

(slide window optimized with hashmap) $O(n)$

减少了平均访问到的状态的个数。

hashmap key是char value是最后一次访问到该char的index。右端指针每前进一位要到hashmap里判断是否出现过。如果出现，左端指针前进到该重复char的最后一次出现的index的后一位。相当于直接跳过了一段与没有包含该重复char的序列。更新hashmap，然后更新maxLen。

时间复杂度分析： 稳定$O(n)$。

C++ 代码

// slide window optimized with hashmap
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        int maxLen = 0;
        unordered_map<char, int> charToIdx;
        for(int i = 0, j = 0; j < n; j++){
            if(charToIdx.count(s[j]))
                i = max(i, charToIdx[s[j]]);
            maxLen = max(maxLen, j-i+1);
            charToIdx[s[j]] = j+1;
        }
        return maxLen;
    }
};

算法4

(slide window fastest) $O(n)$

原理同前。更快了而已。

时间复杂度分析： $O(n)$。

C++ 代码

// slide window quick
class Solution{
public:
int lengthOfLongestSubstring(string s) {
        vector<int> charToIdx(256, -1);
        int maxLen = 0;
        for (int i = -1, j = 0; j != s.length(); j++) {
            if (charToIdx[s[j]] > i)
                i = charToIdx[s[j]];
            charToIdx[s[j]] = j;
            maxLen = max(maxLen, j - i);
        }
        return maxLen;
    }
};

//分析的不对的地方求指正。