Problem Statement in English

You’re given a string s and an array of strings words. All the strings of words are of the same length. A concatenated substring in s is a substring that contains all the strings of words exactly once and without any intervening characters.

Approach

We can solve this problem using a sliding window approach.

The idea is to iterate through the string s and check for all possible starting points of the concatenated substring.

We will use a hash map to keep track of the frequency of each word in words and another hash map to keep track of the words we have seen in the current window.

As we slide the window, we will check if the current word is in the words list. If it is, we will update our seen words and check if we have seen all words. If we have, we will add the starting index of the window to our result list.

If the current word is not in the words list, we will reset our seen words and move the left pointer of the window to the right (current position).

And we’re done!

Solution in Python


class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        if not s or not words:
            return []
        
        word_len = len(words[0])
        num_words = len(words)
        word_map = Counter(words)
        res = []
        
        # Check all possible starting offsets
        for i in range(word_len):
            left = i
            right = i
            seen = Counter()
            count = 0
            
            while right + word_len <= len(s):
                word = s[right : right + word_len]
                right += word_len
                
                if word in word_map:
                    seen[word] += 1
                    count += 1
                    
                    # Shrink window if word frequency exceeds requirement
                    while seen[word] > word_map[word]:
                        left_word = s[left : left + word_len]
                        seen[left_word] -= 1
                        count -= 1
                        left += word_len
                    
                    if count == num_words:
                        res.append(left)
                else:
                    # Reset window if word is not in words
                    seen.clear()
                    count = 0
                    left = right
                    
        return res

Complexity

  • Time: $O(n \cdot m)$
    where $n$ is the length of string $s$ and $m$ is the number of words, as we are iterating through the string and checking each word in the list.

  • Space: $O(m)$
    where $m$ is the number of words in the list words, as we are using a hash map to store the frequency of each word.

Mistakes I Made

My implementation was really overcomplicated.

And we are done.