My accepted Golang solution


  • 0
    V

    The idea is simple; I'm using a sliding window + hashmap of used letters, going from the left to right with two indexes. As soon as I get a repeated character I have to find the index of previous one by moving from left to right and renewing all used characters. The start index of new possible substring will be determined the index of previous repeated character + 1.

    func LengthOfLongestSubstring(str string) int {
    	if len(str) == 0 {
    		return 0
    	}
    	var hash [128]int
    	var (
    		length int
    		result int
    	)
    
    	for k := range str {
    		hash[str[k]] = 1
    	}
    
    	for i, j := 0, 0; i < len(str); i++ {
    		if hash[str[i]] <= 0 {
    			for k := j; j < i; k++ {
    				hash[str[k]] = 1
    				if str[k] == str[i] {
    					j = k + 1
    					break
    				}
    			}
    		}
    
    		if length = i - j + 1; length > result {
    			result = length
    		}
    		hash[str[i]]--
    	}
    
    	return result
    }
    

    After this solution, I've found a bit another one, simpler, but with the same idea:

    func LengthOfLongestSubstring(str string) int {
    	if len(str) == 0 {
    		return 0
    	}
    	var (
    		length int
    		result int
    	)
    
    	hash := make(map[byte]int, len(str))
    
    	for i, j := 0, 0; i < len(str); i++ {
    		if v, ok := hash[str[i]]; ok && v+1 > j {
    			j = v + 1
    		}
    
    		hash[str[i]] = i
    
    		if length = i - j + 1; length > result {
    			result = length
    		}
    	}
    
    	return result
    }
    

Log in to reply
 

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