Substring with Concatenation of All Words
You are given a string s and an array of strings words. All strings in words have the same length.
A concatenated substring is formed by concatenating each word in words exactly once, in any order, without any intervening characters.
Return all starting indices of such concatenated substrings in s.
You may return the answer in any order.
Example 1
Input
barfoothefoobarman 2 foo bar
Output
0 9
Explanation
The substrings starting at indices 0 ("barfoo") and 9 ("foobar") are concatenations of all words exactly once.
Constraints
Hints:
Hint 1
Since all words have the same length, process the string in chunks of that length instead of character by character.
Hint 2
Use a sliding window with a frequency map. Compare the frequency of words in the current window with the required frequencies to determine valid starting indices.
Author & Technical Reviewer
Technically reviewed by: ExamAdda Technical Review Team
Technical Reviewers, ExamAdda
Software engineers at ExamAdda who check every article's definitions, complexity claims and code examples before and after publishing.
Published
Aug 5, 2026
Last updated
Aug 6, 2026
Content Verification Methodology
Definitions and complexity claims were checked against authoritative computer-science references. Code examples were compiled and tested with standard, boundary and edge-case inputs.
Expected Output