0030-substring-with-concatenation-of-all-words¶

Description¶

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 <= 10⁴
1 <= words.length <= 5000
1 <= words[i].length <= 30
s and words[i] consist of lowercase English letters.

Solution(Python)¶

from collections import Counter, defaultdict
class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        #  s = "barfoothefoobarman", words = ["foo","bar"]
        # 
        # 
        #  1. find the concantenetd string in s
        #  2. index
        # 
        #  counter_of _words hahsmp -> frequency
        #    for each index 
        #      run check whether substrings of k is used 
        # Time Compleixty = n.a.b- a.b
        # Space COmplexity: a + b
        # 
        # Sliding window
        #  
        n = len(s)
        k = len(words)
        word_length = len(words[0])
        substring_size = k*word_length
        word_count = Counter(words)
        def slidingwindows(left):
            words_found = defaultdict(int)
            words_used = 0
            excess_word= False

            for right in range(left, n, word_length):
                if right + word_length > n:break

                sub = s[right:right + word_length]

                if sub not in word_count:
                    words_found = defaultdict(int)
                    words_used = 0
                    excess_word= False
                    left = right + word_length 
                else:
                    while right - left == substring_size or excess_word:
                        leftmost_word = s[left : left + word_length]
                        left += word_length
                        words_found[leftmost_word] -= 1

                        
                        if (
                            words_found[leftmost_word]
                            == word_count[leftmost_word]
                        ):
                            # This word was the excess word
                            excess_word = False
                        else:
                            # Otherwise we actually needed it
                            words_used -= 1
                    
                    # Keep track of how many times this word occurs in the window
                    words_found[sub] += 1
                    if words_found[sub] <= word_count[sub]:
                        words_used += 1
                    else:
                        # Found too many instances already
                        excess_word = True

                    if words_used == k and not excess_word:
                        # Found a valid substring
                        ans.append(left)
                        
        ans = []
        for i in range(word_length):
            slidingwindows(i)
        return ans


        