Deciding where a group ends

Look ahead once, then walk forward and let the lookahead tell you when you may stop.

Why it works

One pass to look ahead, one to sweep

First pass: record the last position of each element. That is the lookahead and it costs one scan.

Second pass: walk forward keeping the furthest last-position seen so far. When the current position equals that furthest, nothing inside the current piece extends beyond here, so the piece can close.

That closing condition is the whole algorithm, and it is the same running-maximum shape as the reachability lesson with a different meaning attached.

The lookahead map is the first pass, and it is worth printing on its own before thinking about the sweep.

1text = "abac"2 3last = {ch: index for index, ch in enumerate(text)}     # later wins4print("last occurrence of each:", last)5 6furthest = 07for index, ch in enumerate(text):8    furthest = max(furthest, last[ch])9    closable = index == furthest10    print(f"at {index} ({ch}): must reach at least {furthest}",11          "-> piece may close" if closable else "")

The b is trapped inside the first piece because the a on either side of it holds the piece open.

Find the bug· 5 min

Find the reset bug

This splits a permutation of 0 through n-1 into the largest chunks that can each be sorted on their own. Every size after the first comes out too large. Click the line that is wrong.

Click the line you think is wrong

Problem· 24 min

Partition Labels

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1text = "abac"2 3last = {ch: index for index, ch in enumerate(text)} # later wins4print("last occurrence of each:", last)5 6furthest = 07for index, ch in enumerate(text):8 furthest = max(furthest, last[ch])9 closable = index == furthest10 print(f"at {index} ({ch}): must reach at least {furthest}",11 "-> piece may close" if closable else "")