Split the Tape Into the Most Segments With No Shared Letters
Implement segmentSizes
A tape of lowercase letters is to be cut into consecutive segments so that no letter appears in more than one segment. Cut it into as many segments as possible, and return the length of each segment from left to right.
Searching the tape for each letter's last copy, again and again, works but is quadratic. Recording every letter's last position once turns the job into a single sweep: extend the current segment's end to cover each letter's last copy, and cut whenever the sweep catches up with that end.
Example 1:
Input: tape = "dcdeabfbagghijhkl"
Output: [3,1,5,2,4,1,1]
Example 2:
Input: tape = "abcabc"
Output: [6]
Example 3:
Input: tape = "aabbcc"
Output: [2,2,2]
+ 9 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ tape.length ≤ 40, and tape contains only lowercase English letters - ●
Cut the tape into consecutive segments so that every letter appears in at most one segment (all copies of a letter must end up in the same segment) - ●
Make as many cuts as possible, so that there are as many segments as possible - ●
Return the length of each segment, in order from left to right (the lengths add up to tape.length)
tape =
dcdeabfbagghijhkl