划分字母区间 | 秋招知识库

思路

「同一字母最多出现在一个片段中」意味着，一个片段若要包含字母 $a$ ，那么所有的字母 $a$ 都必须在这个片段中。

示例 1 的 $s = ababcbacadefegdehijhklij$ ，其中字母 $a$ 出现在下标 $0, 2, 6, 8$ 上，那么包含 $a$ 的片段至少要包含区间 $[0, 8]$ 。

把所有出现在 $s$ 中的字母及其下标区间列出来：

字母	下标	下标区间
$a$	$0, 2, 6, 8$	$[0, 8]$
$b$	$1, 3, 5$	$[1, 5]$
$c$	$4, 7$	$[4, 7]$
$d$	$9, 14$	$[9, 14]$
$e$	$10, 12, 15$	$[10, 15]$
$f$	$11$	$[11, 11]$
$g$	$13$	$[13, 13]$
$h$	$16, 19$	$[16, 19]$
$i$	$17, 22$	$[17, 22]$
$j$	$18, 23$	$[18, 23]$
$k$	$20$	$[20, 20]$
$l$	$21$	$[21, 21]$

例如字母 $d$ 的区间为 $[9, 14]$ ，片段要包含 $d$ ，必须包含区间 $[9, 14]$ ，但区间 $[9, 14]$ 中还有其它字母 $e, f, g$ ，所以该片段也必须包含这些字母对应的区间 $[10, 15], [11, 11], [13, 13]$ ，合并后得到区间 $[9, 15]$ 。

将表格中的区间合并为如下几个大区间：

[0, 8], [9, 15], [16, 23]

这些区间满足「同一字母最多出现在一个片段中」的要求，区间长度分别为 $9, 7, 8$ 。

由于题目要求划分出尽量多的片段，而我们又无法将上述区间的任何区间划分开，所以合并后的区间长度即为答案。

算法

遍历 $s$ ，计算字母 $c$ 在 $s$ 中的最后出现的下标 $last [c]$ 。
初始化当前正在合并的区间左右端点 $start = 0, end = 0$ 。
再次遍历 $s$ ，由于当前区间必须包含所有 $s [i]$ ，所以用 $last [s [i]]$ 更新区间右端点 $end$ 的最大值。
如果发现 $end = i$ ，那么当前区间合并完毕，把区间长度 $end - start + 1$ 加入答案。然后更新 $start = end + 1$ 作为下一个区间的左端点。
遍历完毕，返回答案。

Python 解法1C++ 解法1

python

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last = {c: i for i, c in enumerate(s)}  # 每个字母最后出现的下标
        ans = []
        start = end = 0
        for i, c in enumerate(s):
            end = max(end, last[c])  # 更新当前区间右端点的最大值
            if end == i:  # 当前区间合并完毕
                ans.append(end - start + 1)  # 区间长度加入答案
                start = end + 1  # 下一个区间的左端点
        return ans

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int n = s.size();
        int last[26];
        for (int i = 0; i < n; i++) {
            last[s[i] - 'a'] = i; // 每个字母最后出现的下标
        }

        vector<int> ans;
        int start = 0, end = 0;
        for (int i = 0; i < n; i++) {
            end = max(end, last[s[i] - 'a']); // 更新当前区间右端点的最大值
            if (end == i) { // 当前区间合并完毕
                ans.push_back(end - start + 1); // 区间长度加入答案
                start = end + 1; // 下一个区间的左端点
            }
        }
        return ans;
    }
};