Question

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

Examples

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Solution

First solution

create an ASCII table, the value of that array is the index of the string.

class Solution {
public:
    int k=0, a[128] = { 0 };
    int lengthOfLongestSubstring(string s) {
        int ans = 0,i,j=0;
        for (i = 0; i < s.length(); i++) {
            j = max(a[s[i]],j);            //此处j为最大的重复字符的索引
            ans = max(ans,i-j+1);
            a[s[i]] = i+1;
        }
        return ans;
    }
};

Second solution

using an unordered_set as a sliding window and let it iterate through the string.

class Solution {
public:
    static int lengthOfLongestSubstring(string s) {
        int ans = 0, i = 0, j = 0;
        unordered_set<char> set;
        for (j; j<(int)s.length();) {
            if (set.count(s[j])<=0) {   //表中不包含字符
                set.insert(s[j++]);        //sliding window 表尾后移
                ans = max(ans, j - i);       
            }
            else {
                set.erase(s[i++]);         //sliding window 表头后移

            }
        }
        return ans;
    }
};

Third solution

using an unordered_map as a sliding window and let it iterate through the string.

class Solution
{
public:
    static int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> map;
        int i = 0, j = 0, ans = 0;
        for (; i < (int)s.length(); i++) {
            if (map.find(s[i]) != map.end())
            {
                j = max(j, map[s[i]]);
            }
            ans = max(i - j + 1, ans);
            map.erase(s[i]);
            map.insert({ s[i],i+1 });
            
        }
        return ans;
    }
};