Golang map + 2 pointers solution


  • 0

    Based on this solution: https://discuss.leetcode.com/topic/40654/easy-to-understand-ac-c-solution-o-n-k-2-using-map
    It's good to know this solution is generally applicable for similar problems: https://discuss.leetcode.com/topic/30941/here-is-a-10-line-template-that-can-solve-most-substring-problems

    func minWindow(s string, t string) string {
    	requirements := make(map[byte]int)
    	for i := range t {
    		ch := t[i]
    		if cnt, ok := requirements[ch]; !ok {
    			requirements[ch] = 1
    		} else {
    			requirements[ch] = cnt + 1
    		}
    	}
    
    	apperances := make(map[byte]int)
    	counter := len(t)
    	minLen := len(s) + 1
    	resLeft, resRight := 0, 0
    	for left, right := 0, 0; right < len(s); {
    		rch, lch := s[right], s[left]
    
    		if _, ok := requirements[rch]; ok {
    			if cnt, ok := apperances[rch]; !ok {
    				apperances[rch] = 1
    			} else {
    				apperances[rch] = cnt + 1
    			}
    
    			if apperances[rch] <= requirements[rch] && counter != 0 {
    				counter--
    			}
    		}
    
    		if counter == 0 {
    			for {
    				_, ok := requirements[lch]
    
    				if !ok || apperances[lch] > requirements[lch] {
    					if apperances[lch] > requirements[lch] {
    						apperances[lch]--
    					}
    
    					left++
    					lch = s[left]
    				} else {
    					break
    				}
    			}
    
    			if right-left+1 < minLen {
    				resLeft, resRight = left, right+1
    				minLen = right - left + 1
    			}
    		}
    		right++
    	}
    
    	if resLeft == 0 && resRight == 0 {
    		return ""
    	}
    	return s[resLeft:resRight]
    }
    

Log in to reply
 

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