DEV Community

Cover image for LeetCode Challenge 30: Substring with Concatenation of All Words - JavaScript Solution ๐Ÿš€
Rahul Kumar Barnwal
Rahul Kumar Barnwal

Posted on

3 1 1 1 1

LeetCode Challenge 30: Substring with Concatenation of All Words - JavaScript Solution ๐Ÿš€

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".
Enter fullscreen mode Exit fullscreen mode

Example 2

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

Example 3

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

๐Ÿ† 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;
};
Enter fullscreen mode Exit fullscreen mode

๐Ÿ” 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"]
Dry Run
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! ๐Ÿš€


Study

Image of Datadog

The Essential Toolkit for Front-end Developers

Take a user-centric approach to front-end monitoring that evolves alongside increasingly complex frameworks and single-page applications.

Get The Kit

Top comments (1)

Collapse
 
rahulgithubweb profile image
Rahul Kumar Barnwal โ€ข

Follow Me on GitHub ๐Ÿš€

If you found this solution helpful, check out more of my projects and solutions on my GitHub profile.

Don't forget to follow for more updates!

Some comments may only be visible to logged-in visitors. Sign in to view all comments.

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up