跳到主要内容

LeetCode 763. 划分字母区间

本节目标

用字符最后出现位置动态扩张分段右边界，得到尽可能多的合法分段。

这是区间排序与调度中把字符出现范围化为区间的母题。

查看 LeetCode 原题

题意与约束​

把字符串划为尽可能多的连续片段，要求每个字母至多出现在一个片段中，返回各片段长度。题目字符为小写英文字母；空字符串返回空数组。

直接思路与瓶颈​

从当前位置尝试任意切分点，再向后检查前缀字符是否重现，会重复扫描大量后缀。按字符逐个独立分段也不合法：例如 ab...a 中，第一个 a 不能在看到 b 后立即关闭。

贪心模型与算法推导​

先记录每个字符最后一次出现的位置。扫描当前位置 index 时，将当前片段右边界更新为 end=max(end,last[s[index]])；这等价于把当前片段中每个字符的出现区间并起来。只有 index==end 时，所有已见字符都不会在后面出现，才能关闭片段并记录长度。

正确性依据​

当前片段从 start 开始。扫描到任意位置前，end 是其中所有字符最后出现位置的最大值；所以在 end 之前切分必把至少一个字符分到两段，不合法。到达 end 时，每个已见字符的全部出现位置都在 [start,end] 内，切分合法。由于这是第一个可能合法的切分点，立即切分留下最长后缀，因而不会减少后续可切分次数；对后缀重复同一论证即可得到最多片段。

样例执行过程​

字符串 ababcbacadefegdehijhklij 的最后出现位置让边界依次扩张。

  1. 从 a 开始，扫描 a,b,a,b,c,b,a,c,a 后边界被扩张到 8，在索引 8 关闭，长度为 9。
  2. 下一段从 d 开始，字符 d,e,f,e,g,d,e 的最远最后位置为 15，关闭得到长度 7。
  3. 剩余 hijhklij 在索引 23 关闭，长度为 8。

答案为 [9,7,8]。

代码实现​

C++17
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

vector<int> partitionLabels(string s) {
    vector<int> last(26, -1);
    for (int index = 0; index < static_cast<int>(s.size()); ++index) {
        last[s[index] - 'a'] = index;
    }

    vector<int> parts;
    int start = 0;
    int end = 0;
    for (int index = 0; index < static_cast<int>(s.size()); ++index) {
        end = max(end, last[s[index] - 'a']);
        if (index == end) {
            parts.push_back(end - start + 1);
            start = index + 1;
        }
    }
    return parts;
}

复杂度分析​

两次线性扫描，时间 O(n)；C++ 的字母表数组为 O(1) 空间，Python 映射最多保存字符表大小。

边界与易错点​

  • 记录的是最后出现位置，不能只在第一次出现时决定边界。
  • 关闭条件是 index == end，不是扫描到一个新字符时。
  • 单字符字符串返回 [1]；空字符串返回 []。
  • 每次关闭后要把下一段起点设为 index + 1。

模式迁移​

当对象在序列中反复出现、且同一对象不能跨段时，可先把每个对象压缩为“首次到末次”的区间，再用动态右边界合并重叠范围。这是区间覆盖思想在字符串上的轻量变体。