763. 划分字母区间

难度：🟡 Medium | 标签：贪心、哈希 | 状态：⬜ LeetCode 链接

思路

1. 先扫一遍记录每个字母最后出现的位置 last[c]
2. 再扫，维护当前段右界 end = max(end, last[s[i]])，i == end 时切一段

代码

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int last[26] = {};
        for (int i = 0; i < (int)s.size(); ++i) last[s[i] - 'a'] = i;
        vector<int> res;
        int start = 0, end = 0;
        for (int i = 0; i < (int)s.size(); ++i) {
            end = max(end, last[s[i] - 'a']);
            if (i == end) {
                res.push_back(end - start + 1);
                start = i + 1;
            }
        }
        return res;
    }
};

复杂度

• 时间 O(n)，空间 O(1)

易错 / 回顾

• 两遍扫：第一遍预处理，第二遍贪心扩展
• 切段时 start = i + 1，准备下一段
• 类似「合并区间」，但起点是字符的首尾位置