Problem statement

https://leetcode.com/problems/substring-with-concatenation-of-all-words/

Solution

The idea is the following: first, we can divide this problem into several sub-problems, because all words have the same length, barfoothefoobarman is divided into groups{bar, foo, the, foo, bar, man}, {arf, oot, hef, oob, arm} and {rfo, oth, efo, oba, rma} and then problem is similar to 0438, where we need to find anagram substring. We use dictionary with words and number of occurrences and use sliding window technique, keeping number of correct values.

Complexity

Overall complexity of this algorithm is $O(nk)$, where $n$ is size of original string and $k$ is the length of each word. Memory is$O(n)$: on each group we need to keep no more that one copy of string.

Code

class Solution:
    def findSubstring(self, s, words):
        n, k, m = len(s), len(words), len(words[0])
        ans = []
        
        for j in range(m):
            d1, d2 = Counter(words), Counter()
            
            num_to_correct = len(d1)     
            for i in range(j, n, m):
                new_s = s[i:i+m]
                d2[new_s] += 1
                if d1[new_s] == d2[new_s]:
                    num_to_correct -= 1
                if d2[new_s] == d1[new_s] + 1:
                    num_to_correct += 1
                    
                if i - m*k >= 0:
                    old_s = s[i-m*k:i-m*k+m]
                    d2[old_s] -= 1
                    if d2[old_s] == d1[old_s] - 1:
                        num_to_correct += 1
                    if d1[old_s] == d2[old_s]:
                        num_to_correct -= 1
                        
                if num_to_correct == 0:
                    ans.append(i+m-m*k)
                    
        return ans