划分字母区间

怎样从“串划分最多段,每段含某字母仅在该段。”推导出 贪心 · 划分字母区间，并证明每次状态变化都不会漏掉答案？

中心结论：记录每字母最后位置;扫描维护当前段 end, i==end 切段。

这道题考察的是滑动窗口的问题。

给出一个字符串，要求输出满足条件窗口的长度，条件是在这个窗口内，字母中出现在这一个窗口内，不出现在其他窗口内。

在本站主例中，串划分最多段,每段含某字母仅在该段。

算法最终需要得到或观察：划分段列表。

枚举全部决策组合会指数爆炸；贪心只保留能被交换论证或支配关系证明更优的选择。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“局部最优路标”，明确答案需要观察什么。
2. 2状态只维护 last 位置、start/end。
3. 3转移每一步按照 记录每字母最后位置;扫描维护当前段 end, i==end 切段。
4. 4收尾读取 划分段列表。，并复核边界与复杂度。

局部选择必须带着“替换任何其他选择都不会更差”的证明。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：last 位置、start/end。

这一题有 2 种思路，第一种思路是先记录下每个字母的出现次数，然后对滑动窗口中的每个字母判断次数是否用尽为 0，如果这个窗口内的所有字母次数都为 0，这个窗口就是符合条件的窗口。时间复杂度为 O(n)

另外一种思路是记录下每个字符最后一次出现的下标，这样就不用记录次数。在每个滑动窗口中，依次判断每个字母最后一次出现的位置，如果在一个下标内，所有字母的最后一次出现的位置都包含进来了，那么这个下标就是这个满足条件的窗口大小。时间复杂度为 O(n^2)

记录每字母最后位置;扫描维护当前段 end, i==end 切段。

执行过程中持续维护：last 位置、start/end。

正确性依赖以下不变量：段 end 必须是段内所有字母 last 的最大值。

面试时可以压缩为：贪心 O(n)。

落到当前题，执行机制可以压缩为：记录每字母最后位置;扫描维护当前段 end, i==end 切段。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入串划分最多段,每段含某字母仅在该段。 因为：记录每字母最后位置;扫描维护当前段 end, i==end 切段。
2. 2纳入 'a',end 扩展到 8扩展 end。 因为：首次满足 end==i 即最短合法段。
3. 3预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
4. 4纳入 'b',end 扩展到 8扩展 end。 因为：首次满足 end==i 即最短合法段。
5. 5纳入 'c',end 扩展到 8扩展 end。 因为：首次满足 end==i 即最短合法段。
6. 6纳入 'a',end 扩展到 8扩展 end。 因为：首次满足 end==i 即最短合法段。
7. 7i 到达 end=8,切出片段 'ababcbaca'切分并 reset start。 因为：首次满足 end==i 即最短合法段。
8. 8收尾与复杂度划分段列表。 因为：时间 O(n) · 空间 O(1)。记录每字母最后位置;扫描维护当前段 end, i==end 切段。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// 解法一
func partitionLabels(S string) []int {
	var lastIndexOf [26]int
	for i, v := range S {
		lastIndexOf[v-'a'] = i
	}

	var arr []int
	for start, end := 0, 0; start < len(S); start = end + 1 {
		end = lastIndexOf[S[start]-'a']
		for i := start; i < end; i++ {
			if end < lastIndexOf[S[i]-'a'] {
				end = lastIndexOf[S[i]-'a']
			}
		}
		arr = append(arr, end-start+1)
	}
	return arr
}

// 解法二
func partitionLabels1(S string) []int {
	visit, counter, res, sum, lastLength := make([]int, 26), map[byte]int{}, []int{}, 0, 0
	for i := 0; i < len(S); i++ {
		counter[S[i]]++
	}

	for i := 0; i < len(S); i++ {
		counter[S[i]]--
		visit[S[i]-'a'] = 1
		sum = 0
		for j := 0; j < 26; j++ {
			if visit[j] == 1 {
				sum += counter[byte('a'+j)]
			}
		}
		if sum == 0 {
			res = append(res, i+1-lastLength)
			lastLength += i + 1 - lastLength
		}
	}
	return res
}

func main() {
    // 1. 主例
    //    输入：mode="partition-labels", text="ababcbacadefegdehijhklij"
    //    期望：划分段列表。
    //
    // 2. 失败 / 未命中
    //    检查：i 到达 end 才能切。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC56 合并区间；LC435 无重叠
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意串划分最多段,每段含某字母仅在该段。
2. 2重复枚举全部决策组合会指数爆炸；贪心只保留能被交换论证或支配关系证明更优的选择。
3. 3优化记录每字母最后位置;扫描维护当前段 end, i==end 切段。
4. 4证明段 end 必须是段内所有字母 last 的最大值。
5. 5复杂度时间 O(n)，空间 O(1)