partition_labels
1# @leet start 2class Solution: 3 def partitionLabels(self, s: str) -> list[int]: 4 """ 5 To partition a string into as many parts as possible such that each 6 letter appears in at most one part, we want to keep track of the minimum 7 and maximum index each character appears in. 8 9 Next, we want to interpret this as merge intervals, and merge all the 10 overlapping intervals. This works, because we want to take the first interval 11 (say, 0, 8) and then keep adding in the characters until we hit the 8th 12 index. If we encounter a character which has a character outside of our 13 current range, since we must include it, we have to widen our range to include 14 that character. 15 16 If we properly exit our last interval, and there are no characters that 17 have a last occurrence outside said interval, we have created a valid 18 partition. Thus, we can start a new one by just adding our current 19 interval as the new partition. 20 21 We repeat this and then at the end return the distance + 1 for each 22 interval that's left, which solves the problem. 23 """ 24 indexes = {} 25 26 for i, c in enumerate(s): 27 if c in indexes: 28 indexes[c] = [min(i, indexes[c][0]), max(i, indexes[c][1])] 29 else: 30 indexes[c] = [i, i] 31 32 intervals = list(indexes.values()) 33 res = [intervals[0]] 34 35 for start, end in intervals[1:]: 36 prev_start, prev_end = res[-1] 37 if prev_end > start: 38 res[-1] = [prev_start, max(prev_end, end)] 39 else: 40 res.append([start, end]) 41 42 return [end - start + 1 for start, end in res] 43 44 45# @leet end 46 47 48def test(): 49 assert 2 + 2 == 4
class
Solution:
3class Solution: 4 def partitionLabels(self, s: str) -> list[int]: 5 """ 6 To partition a string into as many parts as possible such that each 7 letter appears in at most one part, we want to keep track of the minimum 8 and maximum index each character appears in. 9 10 Next, we want to interpret this as merge intervals, and merge all the 11 overlapping intervals. This works, because we want to take the first interval 12 (say, 0, 8) and then keep adding in the characters until we hit the 8th 13 index. If we encounter a character which has a character outside of our 14 current range, since we must include it, we have to widen our range to include 15 that character. 16 17 If we properly exit our last interval, and there are no characters that 18 have a last occurrence outside said interval, we have created a valid 19 partition. Thus, we can start a new one by just adding our current 20 interval as the new partition. 21 22 We repeat this and then at the end return the distance + 1 for each 23 interval that's left, which solves the problem. 24 """ 25 indexes = {} 26 27 for i, c in enumerate(s): 28 if c in indexes: 29 indexes[c] = [min(i, indexes[c][0]), max(i, indexes[c][1])] 30 else: 31 indexes[c] = [i, i] 32 33 intervals = list(indexes.values()) 34 res = [intervals[0]] 35 36 for start, end in intervals[1:]: 37 prev_start, prev_end = res[-1] 38 if prev_end > start: 39 res[-1] = [prev_start, max(prev_end, end)] 40 else: 41 res.append([start, end]) 42 43 return [end - start + 1 for start, end in res]
def
partitionLabels(self, s: str) -> list[int]:
4 def partitionLabels(self, s: str) -> list[int]: 5 """ 6 To partition a string into as many parts as possible such that each 7 letter appears in at most one part, we want to keep track of the minimum 8 and maximum index each character appears in. 9 10 Next, we want to interpret this as merge intervals, and merge all the 11 overlapping intervals. This works, because we want to take the first interval 12 (say, 0, 8) and then keep adding in the characters until we hit the 8th 13 index. If we encounter a character which has a character outside of our 14 current range, since we must include it, we have to widen our range to include 15 that character. 16 17 If we properly exit our last interval, and there are no characters that 18 have a last occurrence outside said interval, we have created a valid 19 partition. Thus, we can start a new one by just adding our current 20 interval as the new partition. 21 22 We repeat this and then at the end return the distance + 1 for each 23 interval that's left, which solves the problem. 24 """ 25 indexes = {} 26 27 for i, c in enumerate(s): 28 if c in indexes: 29 indexes[c] = [min(i, indexes[c][0]), max(i, indexes[c][1])] 30 else: 31 indexes[c] = [i, i] 32 33 intervals = list(indexes.values()) 34 res = [intervals[0]] 35 36 for start, end in intervals[1:]: 37 prev_start, prev_end = res[-1] 38 if prev_end > start: 39 res[-1] = [prev_start, max(prev_end, end)] 40 else: 41 res.append([start, end]) 42 43 return [end - start + 1 for start, end in res]
To partition a string into as many parts as possible such that each letter appears in at most one part, we want to keep track of the minimum and maximum index each character appears in.
Next, we want to interpret this as merge intervals, and merge all the overlapping intervals. This works, because we want to take the first interval (say, 0, 8) and then keep adding in the characters until we hit the 8th index. If we encounter a character which has a character outside of our current range, since we must include it, we have to widen our range to include that character.
If we properly exit our last interval, and there are no characters that have a last occurrence outside said interval, we have created a valid partition. Thus, we can start a new one by just adding our current interval as the new partition.
We repeat this and then at the end return the distance + 1 for each interval that's left, which solves the problem.
def
test():