Problem Description

You are given a string s and an array of strings words. All the strings of words are of the same length.

A concatenated string is a string that exactly contains all the strings of any permutation of words concatenated.

For example, if words = [“ab”,“cd”,“ef”], then “abcdef”, “abefcd”, “cdabef”, “cdefab”, “efabcd”, and “efcdab” are all concatenated strings. “acdbef” is not a concatenated string because it is not the concatenation of any permutation of words. Return an array of the starting indices of all the concatenated substrings in s. You can return the answer in any order.

Problem Link

Solution 1: Brute Force

Code

func findSubstring(s string, words []string) []int {
    if len(s) == 0 || len(words) == 0 || len(s) < len(words[0]) * len(words) {
        return []int{}
    }

    wordLen := len(words[0])
    m := make(map[string]int)
    for _, v := range words {
        m[v]++
    }
    res := []int{}
    for i := 0; i < len(s); i++ {
        count := 0
        tempM := make(map[string]int)
        for j := i + wordLen; j <= len(s) && count < len(words); j = j + wordLen {
            w := s[j-wordLen:j]
            if m[w] == 0 {
                break
            }
            tempM[w]++
            count++
        }
        if compareTwoMaps(m, tempM) {
            res = append(res, i)
        }
    }
    return res
}

func compareTwoMaps(m1,m2 map[string]int) bool{
    if len(m1) != len(m2) {
        return false
    }
    for k, v := range m1 {
        if m2[k] != v {
            return false
        }
    }
    return true
}

Solution 2: Sliding Window

We can use Sliding Window to solve this issue. In each iteration, there are four important variables:

• Left: the left boundary of the window
• Right: the right boundary of the window
• Count: the number of valid words in the current window
• WindowCount: a map to store the count of each word in the current window We need to control the left and right pointers to solve this issue.

Code

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

    wordLength := len(words[0])
    totalWords := len(words)
    target := make(map[string]int)
    result := make([]int, 0)
    
    for _, word := range words {
        target[word]++
    }
    
    for offset := 0; offset < wordLength; offset++ {
        left := offset
        windowCount := make(map[string]int)
        count := 0
        
        for right := offset; right <= len(s)-wordLength; right += wordLength {
            word := s[right : right+wordLength]
            
            if targetCount, exists := target[word]; exists {
                windowCount[word]++
                count++
                
                for windowCount[word] > targetCount {
                    leftWord := s[left : left+wordLength]
                    windowCount[leftWord]--
                    count--
                    left += wordLength
                }
                
                if count == totalWords {
                    result = append(result, left)
                    leftWord := s[left : left+wordLength]
                    windowCount[leftWord]--
                    count--
                    left += wordLength
                }
            } else {
                clear(windowCount)
                count = 0
                left = right + wordLength
            }
        }
    }