Given a string input_string and a list of strings pattern_list, where each string in pattern_list has the same length, return a list of all starting indices in input_string where a substring exists that is the concatenation of every string in pattern_list in any order, each used exactly once and without any intervening characters. The answer can be returned in any order.
Example 1
Input: input_string=abcabcabc, pattern_list=[abc,abc]
Output: [0,3]
Explanation: Substrings abcabc at index 0 and abcabc at index 3 are valid concatenations.
Example 2
Input: input_string=xyzxyzxyz, pattern_list=[xyz,xyz,xyz]
Output: [0]
Explanation: Only one valid concatenation at index 0.
Example 3
Input: input_string=aabbcc, pattern_list=[aa,bb,cc]
Output: [0]
Explanation: Substring aabbcc at index 0 is a valid concatenation.
Example 4
Input: input_string=abcdef, pattern_list=[gh,ij]
Output: []
Explanation: No valid concatenation exists.
Constraints
Case 1
Input: input_string='testtestest', pattern_list=['test','est']
Expected: [4]
Case 2
Input: input_string='ababab', pattern_list=['ab','ab']
Expected: [0,2]
Case 3
Input: input_string='zzzzzz', pattern_list=['zz','zz','zz']
Expected: [0]
Case 4
Input: input_string='xyxyxyxy', pattern_list=['xy','xy','xy']
Expected: [0,2]
Case 5
Input: input_string='mnopqr', pattern_list=['mn','op','qr']
Expected: [0]