第六天——贪心算法——字符串分隔

1. 题目

给定一个字符串 s，我们需要将其划分为尽可能多的部分，使得同一字母最多出现在一个部分中。

例如：字符串 "ababcc" 可以划分为 ["abab", "cc"]，但要避免 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 这样的划分方式（因为它们包含了同一个字母出现在多个部分的情况）。

注意：划分后的部分顺序必须与原字符串顺序一致，所有部分拼接起来仍然等于 s。
返回：这些部分的长度组成的列表。

2. 分析

这道题目是一个典型的贪心算法问题，解法类似于区间合并问题。

关键思路

1. 记录每个字母的最远出现位置
   • 用 last_occurrence 字典保存每个字符在字符串 s 中最后出现的位置（即最右边的索引），这样可以确定该字符所属的最小子串范围。
2. 滑动窗口遍历，确定当前部分的结束点
   • 用 start 和 end 表示当前部分的起始和结束位置。
   • 遍历字符串时，不断更新 end，使其变为已遍历字符的最远出现位置。
   • 当 i == end 时，说明当前部分可以切分，记录长度，并更新 start 到 end + 1。

3. 完整代码

def partition_labels(s):
    last_occurrence = {char: idx for idx, char in enumerate(s)}  # 记录每个字母的最后出现位置
    start = end = 0
    result = []
    for i, char in enumerate(s):
        end = max(end, last_occurrence[char])  # 更新当前部分的结束点
        if i == end:  # 找到一个符合条件的部分
            result.append(end - start + 1)
            start = end + 1  # 更新下一部分的起始点
    return result
print(partition_labels("ababcc"))

示例分析：s = "ababcc"

1. last_occurrence = {'a': 2, 'b': 3, 'c': 5}
2. 遍历过程：
   • i = 0, char = 'a', end = max(0, 2) = 2
   • i = 1, char = 'b', end = max(2, 3) = 3
   • i = 2, char = 'a'（满足 i == end = 2），记录长度 2 - 0 + 1 = 3（"aba"）❌？
   • （这里需要更正！i = 2 时的 end = 3，不等于 i，不会触发 append。）
   • i = 3, char = 'b'（满足 i == end = 3），记录长度 3 - 0 + 1 = 4（"abab"）
   • i = 4, char = 'c', end = max(3, 5) = 5
   • i = 5, char = 'c'（满足 i == end = 5），记录长度 5 - 4 + 1 = 2（"cc"）
3. 最终结果: [4, 2]（["abab", "cc"]）✅

在 partition_labels 算法中，end 表示当前部分的最远结束位置。为了保证同一字符仅出现在一个部分里，我们需要确保其所有出现的范围都能被当前部分完全覆盖。max(end, last_occurrence[char]) 的作用是不断扩展当前部分的右边界，以确保：当前字符的所有出现都被覆盖，后续字符不会跨越当前部分。

以 s = "ababcc" 为例：

当 i == end 时，触发分隔的原因：

说明：当前部分的所有字符已经处理完毕，

• 已经遍历到 i = end，且在这个位置之前的所有字符的最远出现位置 last_occurrence[char] 都 ≤ end（因为 end 是由 max(last_occurrence[char]) 决定的）。
• 换句话说，这个部分已经囊括了所有必须包含的字符（同一字母的所有出现都被包含在当前部分）。