You are given a string, s, and an array of strings, words. All strings in words are of the same length.

A concatenated string is a string that contains all the words in words exactly once, in any order, concatenated together without any intervening characters.

Formally, a concatenated string is a permutation of all words joined together. For example, if words = ["ab", "cd", "ef"], then the following are all valid concatenated strings: "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", "efcdab". However, "acdbef" is not valid because it is not formed by concatenating all the words in any order.

Your task is to return all starting indices of substrings in s that are concatenated strings.

You may return the indices in any order.

Constraints:

• $1 \leq$ s.length $\leq 10^3$

• $1 \leq$ words.length $\leq 1000$

• $1 \leq$ words[i].length $\leq 30$

• s and words[i] consist of lowercase English letters.

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.