Loading page…
Practice problem · medium
A chat app exports a group conversation as one line of text. Each letter is the initial of the person who wrote a message. The export must be cut into consecutive chunks, and the cuts must follow one rule: each person appears in only one chunk.
Support wants as many chunks as possible, so that each file is small. You get the line, and you return the length of every chunk, from left to right.
Write chunk_sizes(log).
log has lowercase letters only.log into consecutive chunks so that no letter appears in two different chunks.len(log).Input: log = "abacdceffe"
Output: [3, 3, 4]First note the last position of each letter: a at 2, b at 1, c at 5, d at 4, e at 9, f at 8. Scan from the left, keeping the end of the current chunk, which is the furthest last position of the letters seen so far.
| Position | Letter | Chunk end so far | Action |
|---|---|---|---|
| 0 | a | 2 | |
| 1 | b | 2 | |
| 2 | a | 2 | position 2 is the end: close a chunk of 3 |
| 3 | c | 5 | |
| 4 | d | 5 | |
| 5 | c | 5 | close a chunk of 3 |
| 6 | e | 9 | |
| 7 | f | 9 | |
| 8 | f | 9 | |
| 9 | e | 9 | close a chunk of 4 |
Input: log = "abab"
Output: [4]The letter a appears at positions 0 and 2, and b at 1 and 3. Their spans overlap, so nothing can be cut.
Input: log = "abc"
Output: [1, 1, 1]Every letter appears once, so each can be its own chunk.
1 ≤ log.length ≤ 100,000log has the letters a to z only.Trying every cut position and comparing the letters on both sides costs about n × n, which is 10^10 at n = 100,000. Because there are only 26 letters, one scan with a table of last positions costs about n.
chunk_sizes · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.