Top Interview 150

The Substring with Concatenation of All Words problem is a challenging sliding window and hash map problem. Let’s break it down step by step to solve it efficiently.

🚀 Problem Description

Given a string s and an array of strings words:

• Each word in words is of the same length.
• A valid concatenated substring is a substring of s that contains all the strings from words concatenated in any order.
• Return an array of the starting indices of all such substrings in s.

💡 Examples

Example 1

Input: s = "barfoothefoobarman", words = ["foo", "bar"]  
Output: [0, 9]  
Explanation: Substrings starting at indices 0 and 9 are "barfoo" and "foobar".

Example 2

Input: s = "wordgoodgoodgoodbestword", words = ["word", "good", "best", "word"]  
Output: []  
Explanation: No valid concatenation exists.

Example 3

Input: s = "barfoofoobarthefoobarman", words = ["bar", "foo", "the"]  
Output: [6, 9, 12]  
Explanation: Substrings at indices 6, 9, and 12 are valid concatenations.

🏆 JavaScript Solution

To solve this problem efficiently:

• Use a sliding window approach to examine substrings of the same length as the concatenated words.
• Use a hash map to count the occurrences of each word in words.

Implementation

var findSubstring = function(s, words) {
    const wordLength = words[0].length;
    const wordCount = words.length;
    const totalLength = wordLength * wordCount;
    const wordFrequency = {};

    for (let word of words) {
        wordFrequency[word] = (wordFrequency[word] || 0) + 1;
    }

    const result = [];

    for (let i = 0; i < wordLength; i++) {
        let left = i, right = i;
        let windowFrequency = {};
        let count = 0;

        while (right + wordLength <= s.length) {
            const word = s.substring(right, right + wordLength);
            right += wordLength;

            if (wordFrequency[word] !== undefined) {
                windowFrequency[word] = (windowFrequency[word] || 0) + 1;

                if (windowFrequency[word] <= wordFrequency[word]) {
                    count++;
                }

                while (windowFrequency[word] > wordFrequency[word]) {
                    const leftWord = s.substring(left, left + wordLength);
                    windowFrequency[leftWord]--;
                    if (windowFrequency[leftWord] < wordFrequency[leftWord]) {
                        count--;
                    }
                    left += wordLength;
                }

                if (count === wordCount) {
                    result.push(left);
                }
            } else {
                windowFrequency = {};
                count = 0;
                left = right;
            }
        }
    }

    return result;
};

🔍 How It Works

1. Precompute Word Frequencies:

   • Build a hash map wordFrequency to store the count of each word in words.

2. Sliding Window:

   • Slide a window of size totalLength (length of all concatenated words) across the string s. Use a secondary hash map windowFrequency to count occurrences of words within the current window.

3. Shrink or Expand Window:

   • If a word occurs too many times, shrink the window from the left.
   • If all words match, record the starting index.

🔑 Complexity Analysis

• Time Complexity: O(n⋅k), where:

  • n is the length of the string s.
  • k is the length of each word in words.
  • Each character is processed at most once due to the sliding window.

• Space Complexity: O(m+k), where:

  • m is the number of unique words in words.
  • k is the number of words in words.

📋 Dry Run

Input: s = "barfoothefoobarman", words = ["foo", "bar"]

Output: [0, 9]

✨ Pro Tips for Interviews

1. Clarify Constraints:

   • Are all words the same length?
   • Can words contain duplicates?

2. Explain Sliding Window:

   • Highlight why reducing the window avoids unnecessary reprocessing.

3. Discuss Edge Cases:

   • Empty string or empty words.
   • Words longer than s.

📚 Learn More

Check out the full explanation and code walkthrough on my previous Dev.to post:
👉 Longest Substring Without Repeating Characters - JavaScript Solution

What’s your preferred method to solve this problem? Let’s discuss! 🚀