康瑞部落

Longest Substring Without Repeating Characters

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.

解题思路：

1、最直观的想法，每扫描一个字符，与前面最后一个未重复之后的字符比较，直到遇到相同的字符。这里要时刻记录最后一个未重复的字符的位置。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int maxLen = 0;
        int noRepeatStart = 0;
        int len=s.length();
        for(int i=0; i<len; i++){
            char endChar = s[i];
            char localMaxLen = 1;
            for(int j=i-1; j>=noRepeatStart; j--){
                if(s[j]==endChar){
                    noRepeatStart=j+1;
                    break;
                }
                localMaxLen++;
            }
            if(localMaxLen>maxLen){
                maxLen=localMaxLen;
            }
        }
        return maxLen;
    }
};

2、上述代码中，时间复杂度最坏情况是O(n^2)，显然不行，我们可以用一个hash表记录每个字符最后出现的位置。下面是代码。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int maxLen = 0;
        int noRepeatStart = 0;
        int localMaxLen = 0;
        int len=s.length();
        map<char, int> charToIndex;     //某个字符最近出现的位置
        for(int i=0; i<len; i++){
            map<char, int>::iterator it=charToIndex.find(s[i]);
            if(it==charToIndex.end()||it->second<noRepeatStart){
                localMaxLen++;
                if(localMaxLen>maxLen){
                    maxLen=localMaxLen;
                }
            }else{
                noRepeatStart=it->second+1; 
                localMaxLen=i-it->second;
            }
            charToIndex[s[i]]=i;
        }
        return maxLen;
    }
};

3、然而，2方法在leetcode上跑仍然很慢，甚至时间大于1方法。肯定哪里出现问题了。其实char的取值范围最多为256，可以用一个数组来记录每个字符最后出现的位置，这样就省去了map的查找开销。这是一个很好的思路。下面是代码：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int maxLen = 0;
        int noRepeatStart = 0;
        int localMaxLen = 0;
        int len=s.length();
        int charToIndex[256];   //char只有256个
        memset(charToIndex, -1, 256*sizeof(int));
        for(int i=0; i<len; i++){
            if(charToIndex[s[i]]<noRepeatStart){
                localMaxLen++;
                if(localMaxLen>maxLen){
                    maxLen=localMaxLen;
                }
            }else{
                noRepeatStart=charToIndex[s[i]]+1; 
                localMaxLen=i-charToIndex[s[i]];
            }
            charToIndex[s[i]]=i;
        }
        return maxLen;
    }
};

二次刷题（2015-08-17）

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len = s.length();
        int result = 0;
        int charToIndex[256];
        for(int i = 0; i<256; i++){
            charToIndex[i] = -1;
        }
        int start = 0;
        for(int i=0; i<len; i++){
            start = max(start, charToIndex[s[i]] + 1);
            charToIndex[s[i]] = i;
            result = max(i - start + 1, result);
        }
        
        return result;
    }
};