Substring with Concatenation of All Words
Hard · Sliding Window · String · Hash Table · Sliding Window
Problem
You are given a string s and an array words in which every word has the same length. A concatenation of words is any string made by joining all of the words in some order, each word used exactly as many times as it appears in the array. For words = ["ab", "cd", "ab"], both "abcdab" and "ababcd" are concatenations.
Return every starting index in s where a concatenation of words begins, in any order.
Examples
Input: s = "catdogdogcat", words = ["cat","dog"] Output: [0,6]
catdog starts at 0 and dogcat at 6. The window at 3 is dogdog, which uses dog twice.
Input: s = "aaaa", words = ["aa","aa"] Output: [0]
Two copies of aa need all 4 characters, so only the window starting at 0 fits.
Input: s = "abc", words = ["abcd"] Output: []
The string is shorter than the word.
Constraints
- 1 <= s.length <= 10^4
- 1 <= words.length <= 5000
- 1 <= words[i].length <= 30
- All words have the same length
- s and words[i] consist of lowercase English letters
Approaches
- Check every start from scratch — time O(n · m · w), space O(m · w)
Follow-up
With w = 1 this is "find all anagrams of a pattern", a plain character window. If the words had different lengths the alignment trick breaks and the problem becomes a search over ways to cut the string, much like word break.
Related problems
Start free on Cariara · Coding problems · System design studio
