Introduction

In this blog post, we will explore how to solve the LeetCode problem "30" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

You are given a string s and an array of strings words. All the strings of words are of the same length. A concatenated string is a string that exactly contains all the strings of any permutation of words concatenated. For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated string because it is not the concatenation of any permutation of words. Return an array of the starting indices of all the concatenated substrings in s. You can return the answer in any order. Example 1: Input: s = "barfoothefoobarman", words = ["foo","bar"] Output: [0,9] Explanation: The substring starting at 0 is "barfoo". It is the concatenation of ["bar","foo"] which is a permutation of words. The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"] which is a permutation of words. Example 2: Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"] Output: [] Explanation: There is no concatenated substring. Example 3: Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] Output: [6,9,12] Explanation: The substring starting at 6 is "foobarthe". It is the concatenation of ["foo","bar","the"]. The substring starting at 9 is "barthefoo". It is the concatenation of ["bar","the","foo"]. The substring starting at 12 is "thefoobar". It is the concatenation of ["the","foo","bar"]. Constraints: 1 <= s.length <= 104 1 <= words.length <= 5000 1 <= words[i].length <= 30 s and words[i] consist of lowercase English letters.

Explanation

Here's the breakdown of the solution:

• Sliding Window with Frequency Counting: The core idea is to use a sliding window of a size equal to the concatenated length of all words. We then efficiently check if the substring within the window is a valid concatenation of the words by maintaining frequency counts of words.
• Hash Maps for Efficiency: We use hash maps (dictionaries in Python) to store word frequencies. One hash map stores the original word frequencies in the words array, and another hash map tracks the frequencies of words within the current sliding window. This allows for O(1) lookups and updates, making the frequency comparison highly efficient.

• Iterate with Word Length Stride: The algorithm smartly avoids redundant checks by iterating through the string s with a step size equal to the length of each word. This is because if a concatenation starts at index i, any valid concatenation must also start at i + word_length, i + 2 * word_length, and so on.

• Runtime Complexity: O(m n k), where n is the length of s, m is the number of words in words, and k is the length of each word in words. Storage Complexity: O(m), where m is the number of words in words.

Code

    from collections import defaultdict

def find_substring(s, words):
    if not s or not words:
        return []

    word_length = len(words[0])
    num_words = len(words)
    total_length = word_length * num_words
    result = []

    word_counts = defaultdict(int)
    for word in words:
        word_counts[word] += 1

    for i in range(len(s) - total_length + 1):
        seen_words = defaultdict(int)
        words_found = 0
        for j in range(num_words):
            word_index = i + j * word_length
            word = s[word_index:word_index + word_length]

            if word in word_counts:
                seen_words[word] += 1
                if seen_words[word] <= word_counts[word]:
                    words_found += 1
                else:
                    break  # More occurrences than allowed
            else:
                break  # Word not in the list

        if words_found == num_words:
            result.append(i)

    return result