算法

划分字母区间

loser

22 Aug 2026 • 8 min read

给你一个字符串 s。

我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s。

返回一个表示每个字符串片段长度的列表。

示例 1：

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

示例 2：

输入：s = "eccbbbbdec"
输出：[10]

提示：

1 <= s.length <= 500
s 仅由小写英文字母组成

贪心：

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> last(26, 0);

        for (int i = 0; i < s.size(); i++)
        {
            last[s[i] - 'a'] = i;
        }

        vector<int> ans;
        int start = 0;
        int end = 0;

        for (int i = 0; i < s.size(); i++)
        {
            end = max(end, last[s[i] - 'a']);

            if (i == end)
            {
                ans.push_back(end - start + 1);
                start = i + 1;
            }
        }

        return ans;
    }
};

核心思想

这题要求把字符串切成尽可能多的片段，并且同一个字母不能出现在多个片段里。

如果某个片段里包含字母 c，那么这个片段必须覆盖 c 在整个字符串中的最后一次出现位置。

否则，后面还会出现 c，这个字母就会跨越两个片段，划分非法。

所以在确定一个片段时，不能只看当前位置，还要看当前片段内所有字母的最后出现位置。

这题最关键的观察是：

一个片段的右边界，必须至少覆盖片段内所有字母的最后出现位置。

因此可以先记录每个字母最后一次出现的下标。

然后从左到右扫描字符串，维护当前片段最远必须延伸到的位置 end。

当扫描位置 i 正好等于 end 时，说明当前片段内所有字母都不会在后面再次出现，这里就可以切一刀。

为什么要记录最后出现位置

假设字符串是：

s = "ababcc"

字母 a 最后一次出现在下标 2。

字母 b 最后一次出现在下标 3。

如果第一个片段从下标 0 开始，并且包含了 a 和 b，那么它至少要覆盖到下标 3。

否则如果在下标 1 或 2 提前切开，后面还会出现已经在前一个片段中出现过的字母，划分就不合法。

所以需要先用数组 last 记录：

last[s[i] - 'a'] = i;

因为字符串只包含小写英文字母，长度为 26 的数组就够了。

当前片段右边界如何更新

扫描字符串时，用：

end = max(end, last[s[i] - 'a']);

表示当前片段必须至少延伸到 end。

原因是：

当前字符 s[i] 已经出现在当前片段中
那么它最后一次出现的位置也必须包含在当前片段中
所以当前片段右边界至少要到 last[s[i] - 'a']

如果在扫描过程中遇到新的字母，并且它最后出现得更靠后，就继续扩大 end。

为什么 `i == end` 时可以切分

当扫描到位置 i，并且：

i == end

说明从当前片段起点 start 到当前位置 i 之间，所有出现过的字母，它们的最后出现位置都不超过 i。

也就是说，这些字母不会再出现在后面的字符串中。

所以在这里切分不会让任何字母跨越两个片段。

并且为了让片段数量尽可能多，一旦当前位置可以合法切分，就应该马上切分。

当前片段长度是：

end - start + 1

然后下一段从：

i + 1

开始。

为什么贪心选择是安全的

题目要求片段数量尽可能多。

要让片段数量多，就应该让每个片段尽可能短。

对于当前片段来说，end 是必须覆盖到的最早合法右边界。

如果在 end 之前切分，一定会有某个字母还会在后面出现，划分非法。

如果超过 end 再切分，虽然仍然合法，但当前片段变长了，片段数量可能变少。

所以在第一次满足 i == end 的位置切分，是当前片段最早的合法切分点，也是最优选择。

边界情况

如果字符串长度为 1，比如：

s = "a"

字母 a 的最后出现位置就是 0。

扫描到下标 0 时，i == end，切出长度为 1 的片段。

[1]

如果所有字符都互不相同，例如：

s = "abc"

每个字符的最后出现位置都是自己。

所以每个字符都可以单独成段，返回：

[1,1,1]

如果某些字符反复交错出现，例如：

s = "eccbbbbdec"

只要第一个片段包含 e，就必须覆盖到最后一个 e。

中间又包含 c、b、d，它们的最后位置也都在这个范围内。

所以整个字符串只能分成一个片段。

正确性证明

我们证明：算法返回的划分合法，并且片段数量最多。

结论 1：每个生成的片段都是合法的

算法在扫描当前片段时，用 end 记录片段内所有已出现字母的最远最后出现位置。

只有当：

i == end

时，才生成一个片段。

此时当前片段内所有字母的最后出现位置都不超过 i。

因此这些字母不会再出现在后面的片段中。

所以每个字母最多出现在一个片段中，片段合法。

结论 2：算法不会漏掉必须包含在当前片段内的位置

如果当前片段中出现了某个字母 ch，那么这个字母的最后出现位置是：

last[ch]

算法会在扫描到这个字母时执行：

end = max(end, last[ch])

所以当前片段右边界一定会覆盖 last[ch]。

如果后续又遇到其它最后出现位置更靠后的字母，end 也会继续扩大。

因此算法不会在必须包含的位置之前提前切分。

结论 3：每次切分都是当前片段最早的合法切分点

在 i < end 时，说明当前片段中至少有某个字母的最后出现位置还在 i 之后。

如果此时切分，这个字母会跨越两个片段，划分非法。

所以 end 之前都不能切分。

当 i == end 时，根据结论 1，当前位置可以合法切分。

因此 end 就是当前片段最早的合法切分点。

结论 4：最早合法切分能得到最多片段

对于当前片段，如果已经到达最早合法切分点，就立刻切分。

这样剩余未处理字符串最长，后面能够继续划分出的片段数不会变少。

如果延后切分，只会把本可以属于后面片段的字符合并进当前片段，片段数量不会增加。

所以每一步选择最早合法切分点是安全的。

得出结论

由结论 1 可知，算法生成的每个片段都合法。

由结论 2 可知，算法不会漏掉某个字母必须覆盖的最后位置。

由结论 3 可知，每次切分都发生在当前片段最早的合法位置。

由结论 4 可知，这样可以得到最多片段。

因此算法正确。

举例理解

以：

s = "ababcbacadefegdehijhklij"

为例。

先记录每个字母最后一次出现的位置。

第一段从下标 0 开始：

遇到 a，最后位置是 8，所以 end = 8
中间遇到 b、c，它们最后位置都不超过 8
当扫描到下标 8 时，i == end

所以第一段可以切为：

"ababcbaca"

长度是 9。

继续从下标 9 开始：

扫描到 d、e、f、g
当前段右边界最终扩展到下标 15
在下标 15 切出 "defegde"

长度是 7。

剩下部分切出：

"hijhklij"

长度是 8。

最终返回：

[9,7,8]

复杂度分析

第一次遍历记录每个字母最后出现位置。

第二次遍历进行切分。

所以时间复杂度是：

O(n)

只使用长度为 26 的数组 last。

所以空间复杂度是：

O(1)

贪心：