30. Substring with Concatenation of All Words

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

Example:

Input:
  s = "barfoothefoobarman",
  words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

func findSubstring(s string, words []string) []int {
    if len(words) == 0{
        return []int{}
    }
    wordsMap := make(map[string]int, len(words))

    for _,value := range words {
        wordsMap[value] = wordsMap[value] + 1
    }
    var result []int
    wordLen := len(words[0])
    bakWordsMap :=make(map[string]int, len(words))
    for i:=0;i<len(s);i++{
        for loc := i;loc<=len(s) - wordLen;loc+=wordLen{
            word := s[loc:loc+wordLen]
            if _,ok :=wordsMap[word];ok {
                bakWordsMap[word]= bakWordsMap[word] + 1
                wordsMap[word] = wordsMap[word] - 1
                if wordsMap[word] == 0{
                    delete(wordsMap, word)
                }
                
                if len(wordsMap) == 0 {
                    result = append(result, i)
                    break
                }
            } else {
                break
            }
        }
        for s,i := range bakWordsMap {
            wordsMap[s] = wordsMap[s] + i
        }
        bakWordsMap =make(map[string]int, len(words))
    }
    return result
}

func findSubstring(s string, words []string) []int {
    if len(words) == 0{
        return []int{}
    }
    wordsMap := make(map[string]int, len(words))

    for _,value := range words {
        wordsMap[value] = wordsMap[value] + 1
    }
    var result []int
    wordLen := len(words[0])
    bakWordsMap :=make(map[string]int)
    matchCount := len(words)
    for i:=0;i<len(s);i++{
        for loc := i;loc<=len(s) - wordLen;loc+=wordLen{
            word := s[loc:loc+wordLen]
            if v,ok :=wordsMap[word];ok && v>0 {
                bakWordsMap[word]= bakWordsMap[word] + 1
                wordsMap[word] = wordsMap[word] - 1
                matchCount--
                if matchCount == 0 {
                    result = append(result, i)
                    break
                }
            } else {
                break
            }
        }
        matchCount = len(words)
        for s,i := range bakWordsMap {
            wordsMap[s] = wordsMap[s] + i
        }
        bakWordsMap =make(map[string]int)
    }
    return result
}