Golang 2 pointers (sliding window) solution


  • 0

    The idea is pretty much similar as
    https://leetcode.com/problems/minimum-window-substring/
    and the solution described here https://discuss.leetcode.com/topic/30941/here-is-a-10-line-template-that-can-solve-most-substring-problems
    can be applied to this problem as well.

    That is to say, we have two pointers which represents "left index" and "right index" of a window currently we're examining. Then while the windows suffices the condition that the problem asking, we increment the right pointer to seek for a chance to expand the window. Otherwise we increment the left pointer and look for next chance that the window matches the condition again.

    func lengthOfLongestSubstringKDistinct(s string, k int) int {
    	left, right := 0, 0
    	res := 0
    	distMap := make(map[byte]int) // length of this map represents a number of distinct ch
    	for right < len(s) {
    		ch := s[right]
    		if cnt, ok := distMap[ch]; ok {
    			distMap[ch] = cnt + 1
    		} else {
    			distMap[ch] = 1
    		}
    
    		if len(distMap) <= k {
    			if right-left+1 > res {
    				res = right - left + 1
    			}
    		} else {
    			for len(distMap) > k {
    				ch = s[left]
    				distMap[ch] -= 1
    				if distMap[ch] == 0 {
    					delete(distMap, ch)
    				}
    				left++
    			}
    		}
    		right++
    	}
    	return res
    }
    

Log in to reply
 

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