LeetCode: 3_Longest Substring Without Repeating Characters | 求没有重复字符的最长子串的长度 | Medium

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

//方法一：string only
int lengthOfLongestSubstring(string s)
{
    size_t j = 1;
    if (s.size() <= 1)
        return s.size();

    int len = 1, nMaxLen = 0;
    string subStr;
    subStr.push_back(s[0]);
    while (j < s.size()) {
        if (subStr.find(s[j]) == string::npos) {
            subStr.push_back(s[j]);
        }
        else {
            if (len > nMaxLen)
                nMaxLen = len;
            while (subStr.find(s[j]) != string::npos) {
                subStr.erase(0,1);
                len --;
            }
            subStr.push_back(s[j]);
        }
        len ++;
        j ++;
    }
    if (len > nMaxLen)
        nMaxLen = len;
    return nMaxLen;
}

 1 //方法二：pointer
 2 int lengthOfLongestSubstring2(string s) {
 3     int maxlen = 0, left = 0;
 4     int sz = s.length();
 5     int prev[26];
 6     memset(prev, -1, sizeof(prev));
 7 
 8     for (int i = 0; i < sz; i++) {
 9         if (prev[s[i]-'a'] >= left) {
10             left = prev[s[i]-'a'] + 1;
11         }
12         prev[s[i]-'a'] = i;
13         maxlen = max(maxlen, i - left + 1);
14     }
15     return maxlen;
16 }

 1 //方法三：hash table
 2 int lengthOfLongestSubstring3(string s) {
 3     if(s.length()<2)
 4         return s.length();
 5     int max_len=0;
 6     map<char,int> sub; //hash map
 7     for(int i=0,j=0;i<s.length();++i){
 8         if(sub.find(s[i])!=sub.end()){
 9             j=max(j,sub[s[i]]+1);
10         }
11         sub[s[i]]=i;
12         max_len=max(max_len,i-j+1);
13     }
14     return max_len;
15 }