基于贪心算法的字母区间划分

给定一个仅包含小写字母的字符串 S，任务是将其划分为尽可能多的子串，使得每个字母最多只在一个子串中出现。最终输出表示每个子串长度的列表。

贪心算法的核心思想是在每一步选择当前最优解，以期望达到全局最优解。对于本题而言，我们通过记录每个字符在字符串中的最后出现位置，来确定每个片段的边界。具体步骤如下：

1. 遍历字符串，记录每个字符最后出现的位置。
2. 从头开始遍历字符串，维护当前片段的最大右边界。
3. 当遍历到当前片段的最大右边界时，记录该片段的长度，并开始新的片段。

这种策略能确保每个字符只出现在一个片段中，并且尽可能多地划分片段。

vector partitionLabels(string s) {    int n = s.size();    if (n == 1) return {1};    vector ans;    unordered_map last_occurrence; // 记录每个字符最后出现的位置
    // 遍历字符串，记录每个字符最后出现的位置
    for (int i = n - 1; i >= 0; --i) {
        if (last_occurrence.find(s[i]) == last_occurrence.end())
            last_occurrence[s[i]] = i;
    }
    int start = 0, end = 0;
    // 再次遍历字符串，划分片段
    for (int i = 0; i         end = max(end, last_occurrence[s[i]]);
        if (i == end) {
            ans.push_back(end - start + 1);
            start = i + 1;
        }
    }
    return ans;
}

上述代码实现了贪心算法，通过两次遍历字符串完成任务。第一次遍历记录每个字符的最后出现位置，第二次遍历根据这些信息划分片段并计算长度。这种方法不仅高效，而且易于理解。