171. Word Chain Locations
A sign painter has a stack of letter tiles, given as the string parts. Cutting parts into consecutive blocks of exactly w characters gives a list of words (a word may appear several times, and each copy must be used).
A word chain is any string made by joining all of these words, each exactly once, in any order. Given a banner string s, return, in increasing order, every index in s where a word chain begins, meaning the substring starting there, of length parts.length, equals some word chain. Chains may overlap. If no chain exists, return an empty array.
Example 1
- Input:
- s = "dogdogcatdogcatcat", parts = "dogdogcat", w = 3
- Output:
- [0,3]
- Explanation:
The words are dog, dog and cat. The substring at index 0 is dogdogcat and the one at index 3 is dogcatdog, both rearrangements of the words. Index 6 gives catdogcat (two cats), index 9 gives dogcatcat (one dog), so the answer is [0,3].
Example 2
- Input:
- s = "zzzz", parts = "zz", w = 1
- Output:
- [0,1,2]
- Explanation:
The words are z and z. Every substring of length 2 is zz, so a chain starts at indices 0, 1 and 2.
Example 3
- Input:
- s = "abab", parts = "cc", w = 2
- Output:
- []
- Explanation:
The only word is cc, which never appears in the banner, so the result is empty.
Constraints
1 ≤ s.length ≤ 105
1 ≤ w ≤ 30, w ≤ parts.length ≤ 104, and parts.length is a multiple of w
s and parts consist of lowercase English letters.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 3,200 msC++ 800 msJava 1,600 msJavaScript 1,600 msTypeScript 1,600 ms
Expected complexity
- Time
- O(n * w)
- Space
- O(parts.length)