Can You Find Substring with Concatenation of All Words?

A common question in tech interviews involves finding a substring that is a concatenation of a list of words. This scenario helps evaluate a candidate’s problem-solving skills and understanding of string manipulation and data structures. Let’s explore this problem in detail and provide a clear solution.

Problem Statement

You are given a string s and an array of strings words. The goal is to determine if s contains a substring that is a concatenation of each word in words exactly once, without any intervening characters. Each word's length is fixed, and they will appear together as specified by the length of the words.

For instance, if s = "barfoothefoobarman" and words = ["foo", "bar"], the solution should return true since the substring "barfoo" is indeed a concatenation of both "bar" and "foo".

Approach

To solve this problem, an efficient method involves the use of a sliding window technique along with a hash map (or dictionary) for counting the occurrences of the words. The following steps outline the approach:

1. Set Up Variables: Calculate the total length of all words combined and determine the length of each word.
2. Create a Word Count Map: Use a dictionary to count how many times each word appears in the words list.
3. Sliding Window: Iterate through the string s using a fixed-size window of total length for the words. For each position, check if the substring can be broken down into valid words by comparing it to the dictionary.

Code Example

Below is a Python solution that illustrates this approach:

1def findSubstring(s, words):
2    if not s or not words:
3        return []
4    
5    word_length = len(words)
6    word_count = len(words)
7    substring_length = word_length * word_count
8    word_map = {}
9    
10    # Count occurrences of each word in the list
11    for word in words:
12        word_map[word] = word_map.get(word, 0) + 1
13    
14    results = []
15    
16    # Sliding window over the length of the string
17    for i in range(len(s) - substring_length + 1):
18        seen = {}
19        j = 0
20        while j < word_count:
21            # Get the current word from the substring
22            word_index = i + j * word_length
23            current_word = s[word_index:word_index + word_length]
24            
25            if current_word not in word_map:
26                break
27            
28            seen[current_word] = seen.get(current_word, 0) + 1
29            
30            # If any word is seen more than needed
31            if seen[current_word] > word_map[current_word]:
32                break
33            
34            j += 1
35        
36        if j == word_count: # All words matched
37            results.append(i)
38    
39    return results
40
41# Example Usage
42s = "barfoothefoobarman"
43words = ["foo", "bar"]
44print(findSubstring(s, words))  # Output: [0, 9]

Explanation of the Code

1. Input Validation: The function begins with basic checks for empty input.
2. Initialize Parameters: We calculate the lengths we need for words, the word count, and create a dictionary to count the words.
3. Main Loop: The outer loop moves the starting point of the sliding window across s. The inner loop extracts words based on their lengths and checks against the dictionary.
4. Word Matching: It maintains a count of how many times each word is found. If a word exceeds its required count, the inner loop breaks. When all words match exactly, the start index of the substring is stored in the results.

This solution efficiently identifies valid starting indices for substrings that match the criteria, making it a practical choice for similar interview questions.