Loading page…
Practice problem · easy
A parcel-delivery app's conveyor scanner logs a one-letter code each time a parcel passes under it. Sometimes the scanner reads a parcel twice. A double read logs the same code twice in a row, and the two reads cancel each other out.
When two reads cancel, the codes on either side of them become neighbours. If those are equal, they cancel too. Hub staff need the codes that remain, in their original order. A log holds up to 100,000 codes.
Write clean_scan_log(log).
log is a string of lowercase letters. Each letter is one scan code.Input: log = "abbaca"
Output: "ca"| Step | Code read | What happens | Kept codes (bottom to top) |
|---|---|---|---|
| 1 | a |
nothing kept yet: keep it | a |
| 2 | b |
the newest kept code is a: keep it |
a b |
| 3 | b |
equal to the newest kept code b: both cancel |
a |
| 4 | a |
equal to the newest kept code a: both cancel |
empty |
| 5 | c |
nothing kept: keep it | c |
| 6 | a |
the newest kept code is c: keep it |
c a |
The cancelled bb made the two a codes neighbours, and they cancelled too. What remains is ca.
Input: log = "aabb"
Output: ""aa cancels and bb cancels. Nothing remains.
Input: log = "xyz"
Output: "xyz"No two neighbours are equal, so nothing cancels.
1 ≤ length of log ≤ 10^5log contains only the letters a to zA plan that finds one pair, deletes it and scans again costs up to n^2 / 2 steps. For 50,000 nested pairs that is 5 × 10^9, which is too slow.
So read the log once. The new pair that a cancel creates always involves the newest code you kept, so one running list of kept codes is enough.
clean_scan_log · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.