Substring with Concatenation of All Words


#1

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 1:

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.

Example 2:

Input:
  s = "wordgoodstudentgoodword",
  words = ["word","student"]
Output: []

#2

The key here is to observe all the words have the same length. Using this, you can form a word map, check from every character in the string, if the length of the word exists in the map, then check if the no of occurences match.

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

    wl := len(words[0])
    wordMap := make(map[string]int, 0)
    wordsLen := len(words)
    
    for i:=0 ;i<len(words);i++{
        wordMap[words[i]] += 1
    }
    
    // total nof of chars in all words
    totalCharLen := wl * wordsLen
    
    for i:=0;i<len(s) - totalCharLen + 1;i++{
        seen := make(map[string]int, 0)
        j := 0
        for j<wordsLen{
            word := s[i+j*wl:i+(j+1)*wl]
            if _, ok := wordMap[word]; ok {
                seen[word] += 1
                if seen[word] > wordMap[word]{
                    break
                }
            } else{
                break
            }
            j++
        }
        if j==wordsLen{
             result = append(result, i)
        }
    }
    
    return result
}