15. 划分字母区间（763）

一、题目内容 中等

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

示例1：

输入：S = "ababcbacadefegdehijhklij" 输出：[9,7,8] 解释： 划分结果为 “ababcbaca”, “defegde”, “hijhklij”。 每个字母最多出现在一个片段中。 像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。

二、解题思路

这道题的重点在于：判断片段的结束点在哪里？
我们首先要记录每一个字母结束的位置在哪，存起来。
我们知道了s[0]的结束位置是 x，那么我们还需要找 x 位置之前的字母，他们结束的位置 end，然后取最大值。这就是第一个片段了。

那么下一个片段的开始就是start = end + 1，下一个片段的起始字母就是s[start]，找出他的最远位置 x，还是找找 x 位置之前的字母，他们结束的位置 end，取最大值，就是第二个片段。

依次循环，找到结束为止。

三、具体代码

/**
 * @param {string} s
 * @return {number[]}
 */
var partitionLabels = function (s) {
  const hash = new Array(26).fill(0) // 存放 26 个字母的结束位置
  for (let i = 0, len = s.length; i < len; i++) {
    hash[s[i].charCodeAt() - 'a'.charCodeAt()] = i
  }
  let result = []
  let start = 0
  let end = 0
  for (let i = 0, len = s.length; i < len; i++) {
    end = Math.max(hash[s[i].charCodeAt() - 'a'.charCodeAt()], end)
    if (i === end) {
      result.push(end - start + 1)
      start = i + 1
    }
  }
  return result
};

四、其他解法