Golang O(n) with comments


  • 0
    A
    func lengthOfLongestSubstring(s string) int {
    	m := map[byte]struct{}{} // Could maybe get better performance with a slice of 4 int64's (256 bits) as a bit-field
    	max := 0
    	for i, j := 0, 0; j < len(s); j++ {
    		if _, hit := m[s[j]]; hit { // If we have seen the character at j before
    			for ; s[i] != s[j]; i++ { // move i until we find the repeat
    				delete(m, s[i]) // deleting from the map along the way
    			}
    			i++ // finally, step past the repeat
    		} else { // We've never seen this character before
    			m[s[j]] = struct{}{} // add it to the map
    		}
    		if j-i+1 > max { // If this is the biggest so far, update max
    			max = j - i + 1
    		}
    	}
    
    	return max
    }
    

Log in to reply
 

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