题目
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
示例：
输入：S = “ababcbacadefegdehijhklij” 输出：[9,7,8] 解释： 划分结果为 “ababcbaca”, “defegde”, “hijhklij”。 每个字母最多出现在一个片段中。 像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。
提示：
- S的长度在[1, 500]之间。
- S只包含小写字母 ‘a’ 到 ‘z’ 。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/partition-labels 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
由于同一个字母只能出现在同一个片段，显然同一个字母的第一次出现的下标位置和最后一次出现的下标位置必须出现在同一个片段。因此需要遍历字符串，得到每个字母最后一次出现的下标位置。
在得到每个字母最后一次出现的下标位置之后，可以使用贪心的方法将字符串划分为尽可能多的片段，具体做法如下。
- 从左到右遍历字符串，遍历的同时维护当前片段的开始下标 start 和结束下标 end，初始时 start=end=0。
- 对于每个访问到的字母 c，得到当前字母的最后一次出现的下标位置 end_c，则当前片段的结束下标一定不会小于 end_c，因此令 end=max(end,end_c)。
- 当访问到下标 end 时，当前片段访问结束，当前片段的下标范围是 [start,end]，长度为 end−start+1，将当前片段的长度添加到返回值，然后令 start=end+1，继续寻找下一个片段。
- 重复上述过程，直到遍历完字符串。
作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/partition-labels/solution/hua-fen-zi-mu-qu-jian-by-leetcode-solution/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
JS实现
/**
* @param {string} S
* @return {number[]}
*/
var partitionLabels = function (S) {
const result = [];
//使用hashmap记录每一个字符出现的最后位置
const map = new Map();
for (let i = 0; i < S.length; i++) {
map.set(S[i], i);
}
// 默认片段的开始下标，结束下标，都为0
let start = 0,
end = 0;
// 遍历字符串
for (let i = 0; i < S.length; i++) {
end = Math.max(end, map.get(S[i]));
if (i === end) {
result.push(end - start + 1);
start = end + 1;
}
}
return result;
};