Given a string input_string and a list of strings pattern_list, where all strings in pattern_list have the same length, return a list of all starting indices in input_string where a substring is formed by concatenating each string in pattern_list exactly once in any order, without any intervening characters. The answer can be returned in any order.
Example 1
Input: input_string = abcxyzabcxyz, pattern_list = [abc,xyz]
Output: [0,3,6]
Explanation: Substrings at indices 0 (abcxyz), 3 (xyzabc), and 6 (abcxyz) are valid concatenations.
Example 2
Input: input_string = aabbcc, pattern_list = [aa,bb,cc]
Output: [0]
Explanation: Substring at index 0 (aabbcc) is the only valid concatenation.
Example 3
Input: input_string = zzzzzz, pattern_list = [zz,zz]
Output: [0,2]
Explanation: Substrings at indices 0 (zzzz) and 2 (zzzz) are valid concatenations.
Constraints
Case 1
Input: input_string = 'testtesttest', pattern_list = ['test','test']
Expected: [0,4]
Case 2
Input: input_string = 'abcdabcd', pattern_list = ['ab','cd']
Expected: [0,2,4]
Case 3
Input: input_string = 'xyxyxy', pattern_list = ['xy','xy']
Expected: [0,2]
Case 4
Input: input_string = 'abcdef', pattern_list = ['gh','ij']
Expected: []
Case 5
Input: input_string = 'mnopqr', pattern_list = ['mn','op','qr']
Expected: [0]