Substring with Concatenation of All Words

Leetcode Problem 30: Substring with Concatenation of All Words

Problem Summary

Given a string s and an array of equal-length words, find all starting indices in s where a substring is a concatenation of all the words in words exactly once, in any order, with no intervening characters.

Constraints:

• s has between 1 and 10,000 characters, consisting of lowercase English letters.
• There are between 1 and 5,000 words, each of the same length between 1 and 30 characters.
• The total length of all words combined is at most s.length.

Techniques

• Hash Table
• String
• Sliding Window

Solution

function areSubstringMapsEqual(map1: Map<string, number>, map2: Map<string, number>): boolean {
    if (map1.size !== map2.size) { 
        return false
    }

    for (const [key, value] of map1) {
        if (map2.get(key) !== value) { 
            return false
        }
    }

    return true;
}

function findSubstring(s: string, words: string[]): number[] {
    let wordLength = words[0].length
    let wordsLength = words[0].length * words.length
    let wordsWithFrequency = new Map<string, number>()
    let indexes = []

    for (let i = 0; i < words.length; i++) {
        wordsWithFrequency.set(words[i], (wordsWithFrequency.get(words[i]) || 0) + 1)   
    }

    const currentWordsFrequency = new Map<string, number>()

    for (let i = 0; i < wordLength; i++) {
        currentWordsFrequency.clear()
        let left = i
        let right = i

        while (right <= s.length - wordLength) {
            let word = s.substring(right, right + wordLength)
            right = right + wordLength

            if (wordsWithFrequency.has(word)) { 
                currentWordsFrequency.set(word, (currentWordsFrequency.get(word) || 0) + 1)   

                while (currentWordsFrequency.get(word)! > wordsWithFrequency.get(word)!) {
                    let leftWord = s.substring(left, left + wordLength);
                    left += wordLength;
                    
                    currentWordsFrequency.set(leftWord, currentWordsFrequency.get(leftWord)! - 1);
                }

                /// In the best solution, this maps comparison is substituted by a match count
                if (areSubstringMapsEqual(currentWordsFrequency, wordsWithFrequency)) {
                    indexes.push(left)
                }
            } else {
                currentWordsFrequency.clear();
                left = right
            }
        }
    }

    return indexes
};

console.log(findSubstring("barfoothefoobarman", ["foo","bar"]))
console.log(findSubstring("rfoothefoobarman", ["foo","bar"]))