O(n) Python solution with dict


  • 0
    H
    class Solution:
    # @param {string} s
    # @return {integer}
    def lengthOfLongestSubstring(self, s):
    	str1=s
    	cmap={}
    	lastMax,max = 0,0
    	index,start=0,0
    	l = len(s)
    	while index < l:
    		c = s[index]
    		if c not in cmap or cmap[c]<start:
    			max+=1
    			cmap[c]=index
    		else:
    			if max>lastMax:
    				lastMax=max
    			max = index-cmap[c]
    			start= cmap[c]+1
    			cmap[c]=index
    		index+=1
    	if lastMax<max:
    	    lastMax=max
    	return lastMax

  • 0
    H
    int lengthOfLongestSubstring(char* s) {
    int dict[256];
    char c;
    int i=0,lastMax=0,max=0,start=0;
    
    for(i=0;i<256;i++){
        dict[i]=-1;
    }
    i=0;
    while(s[i]!='\0'){
        c = s[i];
        if(dict[c]==-1 || dict[c]<start){
            max++;
        }else{
            if(max>lastMax) lastMax=max;
            max = i-dict[c];
            start=dict[c]+1;
        }
        dict[c]=i;
        i++;
    }
    return lastMax>max?lastMax:max;
    

    }

    the same algorithm in C using 4ms ????


Log in to reply
 

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