Cut the Log Into Exclusive Segments
MediumGreedy
Problem
A server log is a string log of lowercase letters, one letter per event type. You want to cut it into as many contiguous segments as possible so that every event type appears in at most one segment.
Return the lengths of the segments, in order.
Example 1
- Input:
- log = "abacbdeffe"
- Output:
- [5, 1, 4]
"abacb" holds every a, b and c; "d" stands alone; "effe" holds every e and f.
Example 2
- Input:
- log = "mnomxyzyp"
- Output:
- [4, 1, 3, 1]
Constraints
- 1 ≤ log.length ≤ 10^5
- log contains only lowercase English letters
Hint
Show the first hint
Once a segment contains a letter, how far must that segment extend at least?
Walkthrough
How to approach it
01Clarify before coding
- Must every character belong to a segment? Yes, segments cover the whole log.
- Is the answer unique? Yes: the maximum number of segments is achieved by a single partition, the one with the earliest possible cuts.
- Only lowercase letters? Yes, so a 26-entry table is enough.
02Brute force
Try every set of cut positions and keep the largest valid one, or for each candidate cut check letter sets on both sides.
Cost: Exponential for the subset version; O(n² · 26) even for a smarter left-to-right check.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.