hardSliding WindowPure DSA~45 min
Find Substrings Concatenating All Keywords
Given a long log line and a set of equal-length keywords, find every start index where some permutation of all keywords appears as one uninterrupted concatenation.
Problem
You are given a string s and an array words of strings that are all the same length. Return the starting indices of all substrings in s that are a concatenation of every word in words exactly once, in any order, with no characters in between.
Input
A string s and an array words of equal-length strings.
Output
A list of starting indices (any order).
Constraints
- 1 <= s.length <= 10^4
- 1 <= words.length <= 5000
- 1 <= words[i].length <= 30; all words have the same length.
Examples
Example 1
Input
s = "barfoothefoobarman", words = ["foo","bar"]
Output
[0,9]
'barfoo' at 0 and 'foobar' at 9 each use both words once.
Example 2
Input
s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output
[]
No window contains all four words (word appears twice required).