Chunk Concatenation Starts
HardArrays & Hashing
Problem
A log stream s is made of fixed-width tokens. You are given a list words of tokens, all of the same length, possibly with repeats. You want every position where the stream contains all of these tokens back to back, each used exactly as many times as it appears in words, in any order, with nothing in between.
Return all starting indices of such places in s, in ascending order.
Example 1
- Input:
- s = "skyredtanredskytan", words = ["red", "sky", "tan"]
- Output:
- [0, 6, 9]
"skyredtan" at 0, "tanredsky" at 6 and "redskytan" at 9.
Example 2
- Input:
- s = "aaaaaa", words = ["aa", "aa"]
- Output:
- [0, 1, 2]
Every window of length 4 is "aaaa" = "aa" + "aa".
Example 3
- Input:
- s = "abababab", words = ["ab", "ba"]
- Output:
- []
Constraints
- 1 ≤ s.length ≤ 10^4
- 1 ≤ words.length ≤ 5000
- 1 ≤ words[i].length ≤ 30, all equal
- s and words[i] contain lowercase English letters.
Hint
Show the first hint
Since all tokens have the same width w, a match is a window of m · w characters that splits into m tokens at fixed offsets.
Walkthrough
How to approach it
01Clarify before coding
- Are all tokens the same length? Yes, which is what makes the fixed-offset split possible.
- Can words contain repeats? Yes, each copy must be matched.
- Can matches overlap? Yes, report every start index.
02Brute force
For every start i, cut the next m tokens of width w and compare their counts with the counts of words.
Cost: O(n · m · w) time: 10^4 × 5000 × 30 in the worst case, far too slow.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.