题解思路与方法

算法核心

本题等价于经典的 “Partition Labels” 问题。 核心贪心思路：对于每个字符，预先记录其在字符串中最后一次出现的位置；然后从左到右扫描，维护当前分片的区间端点 end。遇到字符 c 时，将 end 更新为 max(end, last[c])。若扫描位置 i 正好等于 end，则可在此处分割一个片段。

实现步骤

1. 预处理：扫描字符串，记录每个字符的最后出现下标 last[c]。

题目内容

公司运动协会正在举办打气球游戏。打气球游戏规则如下：

墙上有一串各种颜色的气球，我们要给他尽可能多的分组，让相同颜色的气球在同一组内。

而且划分完的气球片段按顺序连接起来仍然是原始气球串

请返回一个列表表示划分完的气球片段长度，请注意，如果划分的片段有多个，各个片段之间以逗号和空格分割。

输入描述

一个字符串 $s$ ，代表一串不同颜色的气球。字符串仅仅由小写英文字母组成，$1<=s.length<=500$

输出描述

一个列表，代表划分完之后的每个气球片段的长度。

样例1

输入

abcdeabl

输出

[7, 1]

说明

可以划分为"$abcdeab$"和"$l$"，能保证同一颜色的气球在一个片级中,目获得的片段数量多。两个片段以逗号和空格分割。

样例2

输入

qwerwererrasdfghqccv

输出

[17, 2, 1]

说明

划分结果为"$qwerwererasdfghq$"、"$cc$"、"$v$"。每个颜色的气球只能出现在一个片段中。

像“$qwerwererasdfghgcc$”,"$v$" 这样的划分是错误的，因为划分的片段数不是最多的。三个片段以逗号和空格分割。

样例3

输入

eccbbbbdec

输出

[10]