763. 划分字母区间
难度中等808收藏分享切换为英文接收动态反馈
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
示例：
输入： S = "ababcbacadefegdehijhklij" 输出： [9,7,8] 解释： 划分结果为 "ababcbaca", "defegde", "hijhklij"。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。 复制代码
提示：
S的长度在[1, 500]之间。S只包含小写字母'a'到'z'。
思路
使用贪心的思想寻找每个片段可能的最小结束下标，因此可以保证每个片段的长度一定是符合要求的最短长度，如果取更短的片段，则一定会出现同一个字母出现在多个片段中的情况。由于每次取的片段都是符合要求的最短的片段，因此得到的片段数也是最多的。
var partitionLabels = function(s) { const last = new Array(26); const length = s.length; const codePointA = 'a'.codePointAt(0); for (let i = 0; i < length; i++) { last[s.codePointAt(i) - codePointA] = i; } const partition = []; let start = 0, end = 0; for (let i = 0; i < length; i++) { end = Math.max(end, last[s.codePointAt(i) - codePointA]); if (i == end) { partition.push(end - start + 1); start = end + 1; } } return partition; };
