Loading page…
Practice problem · medium
A monitoring app sends alert messages to a team's phones. One test word must never reach a phone, so the app cuts it out of every message before sending.
Cutting a copy can join the letters on each side into a new copy. The app repeats the cut, always on the leftmost copy, until no copy is left. You are asked to compute what the phone finally shows.
Write strip_banned(message, word).
message and word hold only the letters a to z.word in message and cut it out. The letters on either side close the gap.word no longer appears.Input: message = "daabcbaabcbc", word = "abc"
Output: "dab"A read pointer visits each letter once and copies it to a write pointer. After each copy, if the last three written letters spell abc, the write pointer moves back by three, which cuts them out.
| read | Letter | Written after | Cut? |
|---|---|---|---|
| 0 to 3 | d, a, a, b | daab |
no |
| 4 | c | da |
abc completed: write moves back 3 |
| 5 to 8 | b, a, a, b | dabaab |
no |
| 9 | c | daba |
abc completed: write moves back 3 |
| 10 | b | dabab |
no |
| 11 | c | dab |
abc completed, using the a kept by the last cut: write moves back 3 |
The message that is left is dab.
Input: message = "ababa", word = "aba"
Output: "ba"The copies at positions 0 and 2 overlap. The leftmost one goes first, and ba is left.
Input: message = "abcd", word = "xyz"
Output: "abcd"The word never appears, so nothing is cut.
1 ≤ message.length ≤ 100,000 (letters in one alert)1 ≤ word.length ≤ 50 (letters in the banned word)a to zCutting one copy at a time means searching the message from the start again after every cut. With 50,000 nested copies of a two-letter word, that is about 50,000 searches over a long message: more than 10^9 letter steps. A single walk that compares the last word.length written letters makes at most 100,000 × 50 = 5 × 10^6 comparisons.
strip_banned · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.