How do you solve Substring with Concatenation of All Words on LeetCode?

Substring with Concatenation of All Words (LeetCode #30) can be solved using Brute Force or Optimal Solution (Hash Map). The optimal approach is Optimal Solution (Hash Map) with O(n) time complexity and O(n) space complexity. Key insight: The key observation is that the total length of the substring must be a multiple of the length of the individual words, which allows us to define a fixed window size.

What is the brute force solution for Substring with Concatenation of All Words?

The brute force approach for Substring with Concatenation of All Words is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves generating all possible substrings of the given string `s` that have the same length as the concatenation of all words. We then check if each substring contains all the words exactly once. This method is straightforward but inefficient. The optimal Optimal Solution (Hash Map) approach improves this to O(n).

What algorithm or data structure is used to solve Substring with Concatenation of All Words?

Substring with Concatenation of All Words uses the following concepts: Hash Table, String, Sliding Window. The recommended patterns to study are: Hash Map, Array, Two Pointers.

What are the interview tips for Substring with Concatenation of All Words?

When you first see this problem, clarify the constraints and ask if the words are guaranteed to be of the same length. Communicate your thought process clearly, explaining how you would check for the presence of words in the substring. Mention edge cases such as empty strings or words, and consider cases where no valid substrings exist.

What are common mistakes when solving Substring with Concatenation of All Words?

Students often forget to check the counts of words in the substring, leading to false positives. Another common mistake is not handling edge cases where the string `s` is shorter than the total length of the concatenated words.

#30

Substring with Concatenation of All Words

Hard

Hash TableStringSliding WindowHash MapArrayTwo Pointers

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution (Hash Map)★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a sliding window approach combined with a hash map to keep track of the words and their counts. This allows us to efficiently check if the current substring contains all the words without generating all permutations.

⚙️

Algorithm

4 steps

1Step 1: Create a frequency map of the words.
2Step 2: Use a sliding window of size equal to the total length of the concatenated words.
3Step 3: Move the window across the string, updating the count of words seen in the current window.
4Step 4: If the count of seen words matches the count in the frequency map, record the starting index.

solution.py27 lines

1# Full working Python code with comments
2
3def findSubstring(s, words):
4    if not s or not words:
5        return []
6    word_length = len(words[0])
7    word_count = len(words)
8    total_length = word_length * word_count
9    word_map = {}
10    for word in words:
11        word_map[word] = word_map.get(word, 0) + 1
12    indices = []
13    for i in range(len(s) - total_length + 1):
14        substring = s[i:i + total_length]
15        seen = {}
16        for j in range(0, total_length, word_length):
17            word = substring[j:j + word_length]
18            if word in word_map:
19                seen[word] = seen.get(word, 0) + 1
20                if seen[word] > word_map[word]:
21                    break
22            else:
23                break
24        if seen == word_map:
25            indices.append(i)
26    return indices
27

ℹ

Complexity note: The time complexity is O(n) because we are iterating through the string once and checking the words in constant time using a hash map. The space complexity is O(n) due to the storage of the word frequency maps.

1The key observation is that the total length of the substring must be a multiple of the length of the individual words, which allows us to define a fixed window size.
2Using a hash map to count occurrences of words allows for efficient checking of whether the substring contains all required words.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.