o(n) 8ms but why


  • 0
    L

    I made the first version with c++ as blow which takes 128ms

    int lengthOfLongestSubstring(string s) {
        if(s.size() < 2) return s.size();
        unsigned int maxLen = 0;
        map<char,unsigned int> charLastIndexMap;
        unsigned int begin = 0;
        unsigned int end = 1;
        charLastIndexMap[s[0]] = 1;
    
        while(end != s.size())
        {
            char curChar = s[end];
            if(charLastIndexMap[curChar] == 0 || charLastIndexMap[curChar] < begin)
            {
                charLastIndexMap[curChar] = end+1;
                ++end;
            }
            else
            {
                unsigned int len = end - begin;
                maxLen = (len > maxLen ? len : maxLen);
                begin = charLastIndexMap[curChar];
                charLastIndexMap[curChar] = end+1;
                ++end;
            }
        }
        unsigned int len = end - begin;
        maxLen = (len > maxLen ? len : maxLen);
        return maxLen;
    }
    

    then I changed map to array(takes 16ms)

    int lengthOfLongestSubstring(string s) {
            unsigned int charLastIndex[256];
            memset(charLastIndex,-1,256*sizeof(int));
            unsigned int maxLen = 0,begin = 0,i = 0;
            size_t size = s.size();
            while(i < size){
                if(charLastIndex[s[i]] == -1 || charLastIndex[s[i]] < begin){
                    charLastIndex[s[i]] = i;
                    ++i;
                }else{
                    maxLen = MAX(maxLen,i - begin);
                    begin = charLastIndex[s[i]]+1;
                    charLastIndex[s[i]] = i;
                    ++i;
                }
            }
            maxLen = MAX(maxLen,i-begin);
            return maxLen;
        }
    

    and then I translated it into c(takes 8ms):

    int lengthOfLongestSubstring(char* s) {
        unsigned int charLastIndex[256];
    	memset(charLastIndex,-1,256*sizeof(int));
    	unsigned int maxLen = 0,begin = 0,i = 0;
    	while(s[i]){
    		if(charLastIndex[s[i]] == -1 || charLastIndex[s[i]] < begin){
    			charLastIndex[s[i]] = i;
    			++i;
    		}else{
    		    //printf("%u,%u\n",begin,i);
    		    maxLen = MAX(maxLen,i - begin);
    			begin = charLastIndex[s[i]]+1;
    			charLastIndex[s[i]] = i;
    			++i;
    		}
    	}
    	//printf("%u,%u\n",begin,i);
    	maxLen = MAX(maxLen,i-begin);
    	return maxLen;
    }
    

    and then i simplified it(takes 8ms):

    int lengthOfLongestSubstring(char* s) {
        unsigned int charLastIndex[256];
    	memset(charLastIndex,-1,256*sizeof(int));
    	unsigned int maxLen = 0,begin = 0,i = 0;
    	while(s[i]){
    		if(charLastIndex[s[i]] != -1 && charLastIndex[s[i]] >= begin){
    		    maxLen = MAX(maxLen,i - begin);
    			begin = charLastIndex[s[i]]+1;
    			charLastIndex[s[i]] = i;
    		}
    		charLastIndex[s[i]] = i;
    		++i;
    	}
    	maxLen = MAX(maxLen,i-begin);
    	return maxLen;
    }
    

    and still then i found someone else's code from the discuss group (takes 4ms) section(https://discuss.leetcode.com/topic/20192/4ms-c-code-in-12-lines):

    int lengthOfLongestSubstring(char* s)
    {
    	int len=0;
        char *end=s,*temp;
    	char* addressTable[128]={NULL};
    	while(*end){
    		temp = addressTable[*end];
    		addressTable[*end]=end;
    		if(temp>=s){
        		len=end-s>len?end-s:len;
        		s = temp+1;
    		}
    		end++;
    	}
    	len=end-s>len?end-s:len;
    	return len;
    }
    

    and then I translate it with my own way,but it take still 8 ms.I can not figure out why,who can tell me please:

    #define MAX(a,b) ((a) > (b) ? (a) : (b))
    
    int lengthOfLongestSubstring(char* s) {
        unsigned int charLastIndex[256];
    	memset(charLastIndex,-1,256*sizeof(int));
    	unsigned int maxLen = 0,begin = 0,i = 0,tmp = 0;
    	while(s[i]){
    		 tmp = charLastIndex[s[i]];
    		 charLastIndex[s[i]] = i;
    		 if(tmp != -1 && tmp >= begin){
    		     maxLen = MAX(maxLen,i-begin);
    		     begin = tmp + 1;
    		 }
    		 i++;
    	}
    	maxLen = MAX(maxLen,i-begin);
    	return maxLen;
    }
    

  • 0
    L

    @linuxcoder Because the test cases have been changed, maybe^_^


  • 0
    L

    I think there is no need to memset your array to -1, you just need to add one more.
    C code 6ms

    int lengthOfLongestSubstring(char *s) {
        int max = 0, i = 0, j = 0;
        
        int hash[128] = {0};
        while (s[j]) {
            if (hash[s[j]] != 0) {
                max = (j-i)>max ? (j-i) : max;
                i = hash[s[j]]>i ? hash[s[j]] : i;
            }
            hash[s[j]] = j+1;
            ++j;
        }
        
        return (j-i)>max ? (j-i) : max;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.