Find the starting indices of the substrings in string ( S ) which is made by concatenating all words from a list ( L ) | Returns an integer vector consisting of starting indices of substrings present inside the string S ; Number of a characters of a word in list L . ; Number of words present inside list L . ; Total characters present in list L . ; Resultant vector which stores indices . ; If the total number of characters in list L is more than length of string S itself . ; Map stores the words present in list L against it 's occurrences inside list L ; Traverse the substring ; Extract the word ; If word not found or if frequency of current word is more than required simply break . ; Else decrement the count of word from hash_map ; Store the starting index of that substring when all the words in the list are in substring ; Driver Code
def findSubStringIndices ( s , L ) : NEW_LINE INDENT size_word = len ( L [ 0 ] ) NEW_LINE word_count = len ( L ) NEW_LINE size_L = size_word * word_count NEW_LINE res = [ ] NEW_LINE if size_L > len ( s ) : NEW_LINE INDENT return res NEW_LINE DEDENT hash_map = dict ( ) NEW_LINE for i in range ( word_count ) : NEW_LINE INDENT if L [ i ] in hash_map : NEW_LINE INDENT hash_map [ L [ i ] ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT hash_map [ L [ i ] ] = 1 NEW_LINE DEDENT DEDENT for i in range ( 0 , len ( s ) - size_L + 1 , 1 ) : NEW_LINE INDENT temp_hash_map = hash_map . copy ( ) NEW_LINE j = i NEW_LINE count = word_count NEW_LINE while j < i + size_L : NEW_LINE INDENT word = s [ j : j + size_word ] NEW_LINE if ( word not in hash_map or temp_hash_map [ word ] == 0 ) : NEW_LINE INDENT break NEW_LINE DEDENT else : NEW_LINE INDENT temp_hash_map [ word ] -= 1 NEW_LINE count -= 1 NEW_LINE DEDENT j += size_word NEW_LINE DEDENT if count == 0 : NEW_LINE INDENT res . append ( i ) NEW_LINE DEDENT DEDENT return res NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = " barfoothefoobarman " NEW_LINE L = [ " foo " , " bar " ] NEW_LINE indices = findSubStringIndices ( s , L ) NEW_LINE print ( * indices ) NEW_LINE DEDENT