Loading page…
Practice problem · medium
A chat app has a moderation tool. It looks for a banned word that people hide by changing the order of its letters, so abc may appear as cab or bac.
You get a message log as a string of lowercase letters and a banned word, the probe. You must report every position where the probe appears with its letters in any order.
Write anagram_starts(log, probe).
log is the message text, and probe is the banned word.i counts when the probe.length letters from i to the end of the window use exactly the same letters, with the same counts, as probe.Input: log = "cbaebabacd", probe = "abc"
Output: [0, 6]The trace slides a window of 3 letters over the log. It compares the letter counts of the window with the counts of the probe, which are a: 1, b: 1, c: 1.
| Start | Window | Counts match? |
|---|---|---|
| 0 | cba | yes |
| 1 | bae | no: e instead of c |
| 2 | aeb | no |
| 3 | eba | no |
| 4 | bab | no: b twice |
| 5 | aba | no |
| 6 | bac | yes |
| 7 | acd | no: d instead of b |
Windows at 0 and 6 match, so the output is [0, 6].
Input: log = "ab", probe = "abc"
Output: []The probe is longer than the log, so there is no window, and the output is an empty list.
Input: log = "aaaa", probe = "aa"
Output: [0, 1, 2]Windows at 0, 1 and 2 are all aa, so they all match, and overlapping windows count.
1 ≤ log.length ≤ 100,000 (letters in the log)1 ≤ probe.length ≤ 100,000a to z.Sorting every window costs about n × k log k, which is huge when k is large. Updating counts as the window slides costs one add and one remove per step, and comparing two arrays of 26 counts costs 26 steps. The total is about 26 × 100,000 = 2.6 million steps.
anagram_starts · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.