Partition Labels

Q: Partition Labels 的时间复杂度是多少？

O(n) ：遍历一次记录每个字母最后出现的位置，再遍历一次确定切分位置。无论字符串长度是多少，最后位置表都只有 26 项，因此额外空间复杂度为 O(1) ，不包括输出所占的空间。

Q: Partition Labels 是一道合并区间问题吗？

是的。每个字母覆盖从它第一次出现到最后一次出现的区间，合并重叠的区间就能得到各个部分。贪心遍历就是边遍历边合并，其中 end 表示目前合并区块的右边界。

中等贪心哈希

+10

你会得到一个由小写字母组成的字符串 s。将它切分成尽可能多的连续部分，使每个字母只出现在一个部分中：如果某个字母出现在一个部分中，那么它的所有副本都必须在这个部分中。按从左到右的顺序返回各部分的长度。

函数

partitionLabels(s: string) → integer-array

sstring: 要截取的字符串，只包含小写字母
返回值integer-array: 每个部分的长度，从左到右

约束条件

1 ≤ s.length ≤ 5 × 10⁴
s 中只包含小写英文字母。
这些部分保持原来的顺序，合在一起构成整个 s，所以它们的长度之和等于 s.length。

示例

输入: s = "abacdcefe"
输出: [3, 3, 3]
解释: a 位于 0 和 2，c 位于 3 和 5，e 位于 6 和 8。因此，切分位置在 aba 和 cdc 之后，并且没有任何部分可以再次切分。

提示

逐个打开提示，每个都会多透露一点。

已打开 0/3

题解

只有在两侧都没有同一个字母的位置才允许切分，而最佳答案会在每个这样的位置切分。每到一个位置都重新扫描字符串，时间复杂度会达到平方级。先记录每个字母最后出现的位置，然后从左到右遍历一遍就能找到所有切分位置：每个部分都必须延伸到其中每个字母最后一次出现的位置。

测试每个空缺

结果正确，但无法在最大的测试中运行完毕

思路

如果某个 n-1 个间隙中的间隙两侧没有相同的字母，就可以在这里切开。切开所有允许的位置，就能得到最多的部分：在相邻的两个允许切开的位置之间，每个字母的所有副本都在这一段中，所以这段是有效的部分；而任何有效答案都不能在其他位置切开。

因此，检查每个间隙：分别收集两侧的字母，如果两个集合没有交集，就切开。在 abacdcefe 中，aba 后面的间隙左侧有 a 和 b，右侧有 c、d、e 和 f，因此可以切开。每次检查都会读取整个字符串，总共大约读取 n² 次：当 n = 5 × 10^4 时，是 2.5 × 10^9 次。

算法

将 start = 0，表示当前部分的起始位置。
对于从 1 到 n-1 的每个间隙 cut（即 s[cut] 前面的间隙），标记 s[0..cut-1] 中的字母和 s[cut..n-1] 中的字母。
如果两侧没有共同标记的字母，就将 cut-start 加到答案中，并将 start = cut。
循环结束后，将最后一部分 n-start 加到答案中。

def partitionLabels(s):
    n = len(s)
    sizes = []
    start = 0  # where the current part begins
    for cut in range(1, n):  # the gap just before s[cut]
        left = set(s[:cut])
        right = set(s[cut:])
        if not (left & right):  # no letter on both sides: cut here
            sizes.append(cut - start)
            start = cut
    sizes.append(n - start)  # the last part has no gap after it
    return sizes

合并每个字母的跨度

思路

把每个字母看作从它第一次出现的位置到最后一次出现的位置组成的区间。包含某个字母的部分必须覆盖它的整个区间，因此重叠的区间会属于同一部分，而且重叠会继续扩展：如果 a 与 b 重叠，b 又与 c 重叠，那么这三个字母都属于同一部分。合并所有重叠的区间；每个合并后的区块就是一部分。

合并时需要按区间起点排序，但不必排序就能得到这个顺序：遍历字符串，在字母第一次出现的位置取出它的区间。在 codingisfun 中，i 的区间是 [3, 6]，n 的区间是 [4, 10]，而 g、s、f 和 u 都在 10 之前开始，所以它们会合并成 [3, 10]。字母最多有 26 个，因此位置表的大小是固定的。

算法

遍历一次 s，记录 first 和 last，也就是每个字母第一次和最后一次出现的位置。
再次遍历 s。当位置 i 是对应字母第一次出现的位置时，该字母的区间 [i, last] 就是按起始位置排序后的下一个区间。
如果区间的起始位置在当前块的 end 之后，就结束当前块，长度为 end-start+1，并从 i 开始一个新块。
无论如何，都要设置 end = max(end, last)。
结束最后一个块，并返回各块的长度。

def partitionLabels(s):
    first, last = {}, {}
    for i, c in enumerate(s):
        first.setdefault(c, i)
        last[c] = i
    sizes = []
    start = end = 0  # the block of merged spans being built
    for i, c in enumerate(s):
        if first[c] != i:
            continue  # take each letter's span once, at its first position
        if i > end:  # this span starts after the block: close the block
            sizes.append(end - start + 1)
            start = i
        end = max(end, last[c])
    sizes.append(end - start + 1)
    return sizes

将每个部分扩展到最后一个字母

思路

你不需要最开始的那些位置。从左向右读取，并保留 end，它表示当前部分中任意字母最后出现位置的最远处。每读到一个字母，如果它最后一次出现的位置更远，就将 end 扩展到该位置。

当 i 到达 end 时，这部分中的每个字母最后一次出现的位置都在 i 处或之前，因此 i 后面的间隔是允许的。在此之前，你读到的某个字母仍会在右侧再次出现，所以这部分中更早的间隔都不允许。遍历过程会恰好在允许的间隔处切分。在 abacdcefe 中，a 会将 end 设为 2，这部分在 i = 2 时结束；c 会将它设为 5，下一部分在 5 处结束。

算法

只需遍历一次，将每个字母 c 的最后出现位置存入长度为 26 的数组 last[c]。
设置 start = 0 和 end = 0。
对于每个位置 i，设置 end = max(end, last[s[i]])。
如果 i == end，将 end-start+1 加到答案中，并设置 start = i+1。
返回这些长度。

def partitionLabels(s):
    last = {c: i for i, c in enumerate(s)}  # last position of each letter
    sizes = []
    start = end = 0
    for i, c in enumerate(s):
        end = max(end, last[c])  # the part must reach c's last copy
        if i == end:  # no letter of this part appears later
            sizes.append(end - start + 1)
            start = i + 1
    return sizes

易错点和边界情况

在当前字母最后一次出现的位置切分，而不是在这一部分的 end 处切分。在 abcba 中，索引 2 处的 c 是它最后一次出现的位置，但在那里切分会把两个 a 和两个 b 分开。
长度差 1：从 start 到 end（包含两端）的部分有 end-start+1 个字母。
返回切分位置，而不是长度。对于 abacdcefe，答案是 [3, 3, 3]，而不是 [2, 5, 8]。
在间隔版本中忘记最后一部分。最后一部分后面没有间隔，所以要在循环后加上 n-start。

常见问题3

Partition Labels 的时间复杂度是多少？

O(n)：遍历一次记录每个字母最后出现的位置，再遍历一次确定切分位置。无论字符串长度是多少，最后位置表都只有 26 项，因此额外空间复杂度为 O(1)，不包括输出所占的空间。

Partition Labels 是一道合并区间问题吗？

是的。每个字母覆盖从它第一次出现到最后一次出现的区间，合并重叠的区间就能得到各个部分。贪心遍历就是边遍历边合并，其中 end 表示目前合并区块的右边界。

Partition Labels 可以返回多少个部分？

介于 1 和 26 之间。每个部分都至少拥有一个只出现在该部分中的字母，而小写字母只有 26 个。每个字母都恰好出现一次的字符串会得到 26 个长度为 1 的部分；以同一个字母开头和结尾的字符串会得到一个部分。

def partitionLabels(s):
    # 在这里编写代码

测试 #1

测试 #2

测试 #3

参数

s = "abacdcefe"

预期输出

[3, 3, 3]