Write a Python program to return an array of the starting indices of all concatenated substrings in the given string. Input: string = '123456876456123987', words = ['123','456']. Output: [0,9]. Explanation: The substring starting at 0 is '123456'. It is the concatenation of ['123','456'] which is a permutation of words. The substring starting at 9 is '456123'. It is the concatenation of ['456','123'] which is a permutation of words.

The problem is a classic sliding‑window search for all permutations of a list of words. Each word has the same length, so the total length of a concatenated substring is len(words) * word_len. We slide a window of that size over the string, maintaining a frequency map of the words seen in the current window. If the map matches the target word frequency map, we record the start index.

Algorithm:

1. Compute word_len and total_len.
2. Build a dictionary need counting each word in words.
3. For each possible start index i from 0 to len(s)-total_len:

• Initialize an empty dictionary seen.
• For each word position j in the window (0 to len(words)-1):

  Extract the word w = s[i + jword_len : i + (j+1)*word_len].
 * Increment seen[w].
 * If seen[w] exceeds need[w], break early.

• After the inner loop, if seen == need, append i to result.

1. Return the result list.

Complexity: We examine each window in O(m) time where m is the number of words. The outer loop runs O(n) times, so total time is O(n*m). Space usage is O(k) for the hash maps, where k is the number of distinct words.

Python code:

from collections import Counter

def find_concat_indices(s, words):
    if not s or not words:
        return []
    word_len = len(words[0])
    total_len = word_len * len(words)
    need = Counter(words)
    res = []
    for i in range(len(s) - total_len + 1):
        seen = Counter()
        for j in range(len(words)):
            w = s[i + j*word_len : i + (j+1)*word_len]
            seen[w] += 1
            if seen[w] > need[w]:
                break
        else:
            if seen == need:
                res.append(i)
    return res

print(find_concat_indices('123456876456123987', ['123','456']))
# Output: [0, 9]