Share my solution O(n) 4ms in C language


  • 5
    L
    int lengthOfLongestSubstring(char *s) {
        int maxLen = 0;
        int pre = -1;
        int hash[128];
        memset(hash, -1, sizeof(hash));
    
        int i,c;
        for(i=0; c=s[i]; i++)
        {
            if(pre < hash[c] && hash[c]!=-1)
                pre = hash[c];
            maxLen = maxLen>(i-pre)? maxLen : (i-pre);
    
            hash[c] = i;
        }
    
        return maxLen;
    }

  • 1
    R

    Mine are of 4ms but, there are some minor optimization, here the modification is that, not always update the maxSeen, just updating it while occur a repeating period & once after the string traverse ended.

    int lengthOfLongestSubstring(char *s)
    {
    	int maxSeen = 0;
    	int start = -1;
    	
    	int lastSeenIndex[256];
    	memset(lastSeenIndex, -1, sizeof(lastSeenIndex));
    
    	int index = 0;
    	char c;
    	for(; c = s[index]; index++)
    	{
    		if(lastSeenIndex[c] != -1 && start < lastSeenIndex[c] )
    		{
    			//here we got a reprating period of the same char
    
    			int tmpMax = index - start - 1;//lenght just before the repeat
    					
    			start = lastSeenIndex[c];
    			
    			maxSeen = (tmpMax > maxSeen) ? tmpMax : maxSeen;
    		}
    
    		lastSeenIndex[c] = index;
    	}
    
    	//for the last one
    	int tmpMax = index - start - 1;
    	maxSeen = (tmpMax > maxSeen) ? tmpMax : maxSeen;
    	
    	return maxSeen;
    	
    }

Log in to reply
 

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