Substring with Concatenation of All Words

Problem

You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.

You can return the answer in any order.

Examples

Example 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []

Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]

Solution

Method 1 - Sliding Window

This problem is similar (almost the same) to [Longest Substring with At Most K Distinct Characters](longest-substring-with-at-most-k-distinct-characters) OR [Minimum Window Substring](minimum-window-substring).

To find all the starting indices of substring(s) that are concatenations of all words in the input array:

1. Calculate the length of each word and the total length of the concatenated substring.
2. Use sliding window technique to traverse through the string s.
3. For each window, check if the concatenation of words is valid by maintaining a frequency count of words and matching it with the words in the current window.

Approach

1. Initial Setup:

   • Calculate the length of each word (they are the same).
   • Calculate the total length needed for the concatenation of all words.
   • Create a frequency count of the words in the array.

2. Sliding Window:

   • Traverse through the string s using a sliding window to extract substrings of the total length.
   • For each window, validate if it matches the words' frequency.

3. Validation:

   • For each window substring, divide it into parts of the word's length.
   • Check if the frequency of these parts matches with the frequency of words in the array.

Code

Java

public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ans = new ArrayList<>();
        if (s == null || s.isEmpty() || words == null || words.length == 0) return ans;

        int wordLength = words[0].length();
        int wordsCount = words.length;
        int totalLength = wordLength * wordsCount;

        Map<String, Integer> wordMap = new HashMap<>();
        for (String word : words) {
            wordMap.put(word, wordMap.getOrDefault(word, 0) + 1);
        }

        for (int i = 0; i <= s.length() - totalLength; i++) {
            String substring = s.substring(i, i + totalLength);
            if (isValid(substring, wordMap, wordLength)) {
                ans.add(i);
            }
        }

        return ans;
    }

    private boolean isValid(String substring, Map<String, Integer> wordMap, int wordLength) {
        Map<String, Integer> seenWords = new HashMap<>();
        for (int j = 0; j < substring.length(); j += wordLength) {
            String word = substring.substring(j, j + wordLength);
            seenWords.put(word, seenWords.getOrDefault(word, 0) + 1);
        }
        return seenWords.equals(wordMap);
    }
}

Python

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        if not s or not words:
            return []
        
        word_length = len(words[0])
        words_count = len(words)
        total_length = word_length * words_count
        ans = []

        word_map: Dict[str, int] = {}
        for word in words:
            word_map[word] = word_map.get(word, 0) + 1

        for i in range(len(s) - total_length + 1):
            substring = s[i:i + total_length]
            if self.is_valid(substring, word_map, word_length):
                ans.append(i)
        
        return ans

    def is_valid(self, substring: str, word_map: Dict[str, int], word_length: int) -> bool:
        seen_words: Dict[str, int] = {}
        for j in range(0, len(substring), word_length):
            word = substring[j:j + word_length]
            if word in word_map:
                seen_words[word] = seen_words.get(word, 0) + 1
                if seen_words[word] > word_map[word]:
                    return False
            else:
                return False
        return seen_words == word_map

Complexity

• ⏰ Time complexity: O(n * m * l) where n is the length of the string s, m is the number of words, and l is the length of each word.
• 🧺 Space complexity: O(n * m * l) where n is the length of the string s, m is the number of words, and l is the length of each word.