Longest substring without repeating characters

medium 原题链接：https://leetcode.com/problems/longest-substring-without-repeating-characters/

Longest substring without repeating characters

原题链接

描述

Given a string s, find the length of the longest substring without repeating characters.

例子

Input: s = "abcabcbb"

Output: 3

Explanation: The answer is "abc", with the length of 3.

解法： Brute Force （Time Limit Exceeded）

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        int ans = 0;
        for(int i=0; i<n; i++){
            for(int j=i+1; j<=n; j++){
                if(allUnique(s,i,j)) ans=max(ans,j-i);
            }
        }
        return ans;
    }
    
    bool allUnique(string s,int start, int end){
        unordered_set<char> seen;
        for(int i=start; i<end; i++){
            char ch=s[i];
            if(seen.count(ch))return false;
            seen.insert(ch);
        }
        return true;
    }
};

分析：time：O（n^3），space：O(min(m,n))

解法：slide window

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        unordered_set<char> seen;
        int ans = 0,i=0,j=0;
        while(i<n&&j<n){
            if(!seen.count(s[j])){
                seen.insert(s[j++]);
                ans=max(ans,j-i);
            }else{
                seen.erase(s[i++]);
            }
        }
        return ans;
    }
};

分析：time：O(2n)=O(n)；space：O(min(m,n))。

解法：slide window optimized

class Solution {
public:
     int lengthOfLongestSubstring(string s) {
           int res = 0, left = 0, right = 0;
           unordered_map<char, int> map;
           while (right < s.size() && left + res < s.size()) {
               if (map.find(s[right]) != map.end()) {
                   left = max(left, map[s[right]] + 1);
               }
               map[s[right]] = right;
               res = max(res, right - left + 1);
   			right++;
           }

           return res;
       }
};

解法 ASCII 表

class Solution {
public:
     int lengthOfLongestSubstring(string s) {
         int n = s.length(), ans = 0;
         vector<int> index;
         index.assign(128,0);
        // current index of character
        // try to extend the range [i, j]
         for (int j = 0, i = 0; j < n; j++) {
            i = max(index[s[j]], i);
            ans = max(ans, j - i + 1);
            index[s[j]] = j + 1;
         }
        return ans;
    }
};