Split String Into Blocks
Problem
Cut a lowercase string into as many pieces as possible so that every letter appears in at most one piece. Joining the pieces back together must rebuild the original string exactly. Return the length of each piece, in order.
Examples
Input: s = "abacdc"
Output: [3, 3]
Why: "aba" holds every a and b, "cdc" holds every c and dInput: s = "abcabc"
Output: [6]
Why: every letter reappears late, so no cut is legalInput: s = "xyz"
Output: [1, 1, 1]
Why: edge case, no letter repeats so every character is its own pieceHints
0 / 3
A cut is only legal at a position where nothing to the left reappears to the right. Ask what you would need to know about each letter to test that instantly.
One pre-pass over the string can record the final index of every letter. After that the test becomes a comparison between two numbers.
Walk the string keeping the furthest final index among the letters seen since the last cut. The moment the current index equals that number, close the piece here and start the next one.
Solution
Record each letter's last index in a first pass. Then sweep once, stretching a running boundary to the last index of every letter met since the previous cut. Reaching that boundary means every letter inside the piece is finished, so cutting here is legal — and cutting at the first legal point is what maximises the number of pieces, since waiting longer only merges two pieces into one. Both passes are linear, so time is O(n) and space is O(1) for the fixed 26-letter map.
def block_sizes(s):
last = {ch: i for i, ch in enumerate(s)} # final index of each letter
sizes, start, end = [], 0, 0
for i, ch in enumerate(s):
end = max(end, last[ch]) # the piece cannot close before this
if i == end: # every letter inside is finished
sizes.append(i - start + 1)
start = i + 1
return sizes
print(block_sizes("abacdc")) # -> [3, 3]
print(block_sizes("abcabc")) # -> [6]
print(block_sizes("xyz")) # -> [1, 1, 1]Stuck on the idea rather than the code? What Makes Greedy Work covers it.