Split the Tape Into the Most Segments With No Shared Letters
Solve this ProblemA 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.
Test Case 1:
Test Case 2:
Test Case 3:
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)
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Rescan the Whole Tape to Find Each Letter's Last Copy
BruteBuild the segments one at a time. A segment starts where the previous one ended. Look at its first letter and find that letter's last occurrence in the whole tape by searching (so the segment must reach at least that far). Then look at every letter inside the segment so far — as the segment stretches, more letters come inside, each of which may push the end further right. When every letter in [start, end] has been checked and none reaches beyond end, the segment is complete: record its length and start the next one. Each lookup of a last occurrence is a search over the tape, which is what makes this quadratic.
O(n²)O(1) extra1class Solution {
2 public List<Integer> segmentSizes(String tape) {
3 List<Integer> sizes = new ArrayList<>();
4 int n = tape.length();
5 int start = 0;
6 while (start < n) {
7 int end = start;
8 for (int i = start; i <= end; i++) {
9 int last = tape.lastIndexOf(tape.charAt(i));
10 if (last > end) end = last;
11 }
12 sizes.add(end - start + 1);
13 start = end + 1;
14 }
15 return sizes;
16 }
17}Optimal — Remember Each Letter's Last Position, Then Sweep Once
OptimalDo the searching once: a single pass records the last position of each of the 26 letters. Then sweep the tape left to right keeping the end of the current segment: for every character, push the end out to that character's last position if it is farther. When the sweep reaches the current end, every letter seen since the segment began has all its copies inside — cut here, record the length and begin the next segment. Two passes, no repeated searching.
O(n)O(1)1class Solution {
2 public List<Integer> segmentSizes(String tape) {
3 int n = tape.length();
4 int[] last = new int[26];
5 for (int i = 0; i < n; i++) last[tape.charAt(i) - 'a'] = i;
6 List<Integer> sizes = new ArrayList<>();
7 int start = 0, end = 0;
8 for (int i = 0; i < n; i++) {
9 end = Math.max(end, last[tape.charAt(i) - 'a']);
10 if (i == end) {
11 sizes.add(end - start + 1);
12 start = i + 1;
13 }
14 }
15 return sizes;
16 }
17}