Substring with Concatenation of All Words

• Get the number of words numWords, the length of each word wordLen, and the total length of the concatenated substring substringLen.
• Create a frequency map wordCount for the words in the words array.
• Initialize an empty list result to store the starting indices.
• Iterate through the string s from index i = 0 to s.length() - substringLen.
• For each i, extract the substring of length substringLen.
• Create a new frequency map wordsSeen for the words within this substring by breaking it into chunks of wordLen.
• Compare the wordsSeen map with the wordCount map.
• If the maps are identical, add the index i to the result list.
• Return the result list after checking all possible indices.

The method begins by pre-calculating essential values: numWords (the count of words), wordLen (the length of a single word), and substringLen (the total length of the target substring). A reference frequency map, wordCount, is created from the input words array to know what a valid permutation should contain.

The main part of the algorithm is a loop that iterates through s from index 0 up to the last possible starting point for a valid substring. In each iteration, a substring of length substringLen is extracted. To verify if this substring is a valid concatenation, we build a second frequency map, wordsSeen, by chopping the substring into wordLen-sized chunks and counting them. Finally, we compare wordsSeen with wordCount. If they are equal, the starting index i is a valid solution and is added to our results.

1import java.util.ArrayList;2import java.util.HashMap;3import java.util.List;4import java.util.Map;5 6class Solution {7    public List<Integer> findSubstring(String s, String[] words) {8        if (s == null || s.length() == 0 || words == null || words.length() == 0) {9            return new ArrayList<>();10        }11 12        int wordLen = words[0].length();13        int numWords = words.length;14        int substringLen = wordLen * numWords;15        List<Integer> result = new ArrayList<>();16 17        if (s.length() < substringLen) {18            return result;19        }20 21        Map<String, Integer> wordCount = new HashMap<>();22        for (String word : words) {23            wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);24        }25 26        for (int i = 0; i <= s.length() - substringLen; i++) {27            Map<String, Integer> wordsSeen = new HashMap<>();28            for (int j = 0; j < numWords; j++) {29                int wordStart = i + j * wordLen;30                String word = s.substring(wordStart, wordStart + wordLen);31                wordsSeen.put(word, wordsSeen.getOrDefault(word, 0) + 1);32            }33 34            if (wordCount.equals(wordsSeen)) {35                result.add(i);36            }37        }38 39        return result;40    }41}

• Pre-calculate wordLen, numWords, and create a reference frequency map wordCount from words.
• Loop i from 0 to wordLen - 1. This outer loop handles all possible word alignments.
• For each i, initialize a sliding window with left = i, wordsFound = 0, and an empty seenWords map.
• Use a second pointer j to slide through the string from i in steps of wordLen.
• At each step j, extract the word.
• If word is in wordCount:
  • Update its count in seenWords and increment wordsFound.
  • If the count of word in seenWords exceeds wordCount, shrink the window from the left until it's valid again, updating seenWords and wordsFound.
  • If wordsFound equals numWords, a valid substring is found. Add left to the results, and slide the window one step to the right to continue the search.
• If word is not in wordCount, reset the window and maps, and move left to the position after the invalid word.
• Return the collected results.

The key insight is that we don't need to check every single starting index. A valid substring starting at index k will be composed of words at k, k+L, k+2L, ... where L is wordLen. This means we can iterate through the string L times, once for each possible remainder modulo L (i.e., i = 0, 1, ..., L-1).

For each starting offset i, we use a sliding window. We maintain a left pointer for the start of the window and a j pointer for the end. We slide j through the string in steps of L. We use a seenWords map to track word frequencies within the current window.

• When a new word (at j) enters the window, we update seenWords.
• If the new word is not in our target wordCount map, the window is invalid, so we reset it.
• If a word's count in seenWords becomes too high, we shrink the window from the left until the counts are valid.
• When the number of valid words in our window (wordsFound) reaches numWords, we've found a solution. We record the left index and then slide the window by one word to search for the next potential match.

This avoids re-computation and brings the complexity down significantly.

1import java.util.ArrayList;2import java.util.HashMap;3import java.util.List;4import java.util.Map;5 6class Solution {7    public List<Integer> findSubstring(String s, String[] words) {8        if (s == null || s.length() == 0 || words == null || words.length == 0) {9            return new ArrayList<>();10        }11 12        Map<String, Integer> wordCount = new HashMap<>();13        for (String word : words) {14            wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);15        }16 17        int wordLen = words[0].length();18        int numWords = words.length;19        List<Integer> result = new ArrayList<>();20 21        for (int i = 0; i < wordLen; i++) {22            int left = i;23            int wordsFound = 0;24            Map<String, Integer> seenWords = new HashMap<>();25 26            for (int j = i; j <= s.length() - wordLen; j += wordLen) {27                String word = s.substring(j, j + wordLen);28 29                if (wordCount.containsKey(word)) {30                    seenWords.put(word, seenWords.getOrDefault(word, 0) + 1);31                    wordsFound++;32 33                    while (seenWords.get(word) > wordCount.get(word)) {34                        String leftWord = s.substring(left, left + wordLen);35                        seenWords.put(leftWord, seenWords.get(leftWord) - 1);36                        wordsFound--;37                        left += wordLen;38                    }39 40                    if (wordsFound == numWords) {41                        result.add(left);42                        String leftWord = s.substring(left, left + wordLen);43                        seenWords.put(leftWord, seenWords.get(leftWord) - 1);44                        wordsFound--;45                        left += wordLen;46                    }47                } else {48                    seenWords.clear();49                    wordsFound = 0;50                    left = j + wordLen;51                }52            }53        }54        return result;55    }56}