划分字母区间

Tips

题目类型: Greedy

题目

给你一个字符串 s. 我们要把这个字符串划分为尽可能多的片段, 同一字母最多出现在一个片段中.

注意, 划分结果需要满足: 将所有划分结果按顺序连接, 得到的字符串仍然是 s.

返回一个表示每个字符串片段的长度的列表.

提示:

• 1 <= s.length <= 500
• s 仅由小写英文字母组成

示例

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

输入: s = "eccbbbbdec"
输出: [10]

题解

由于同一个字母只能出现在同一个片段, 显然同一个字母的第一次出现的下标位置和最后一次出现的下标位置必须出现在同一个片段. 因此需要遍历字符串, 得到每个字母最后一次出现的下标位置.

接下来就是贪心法, 找到最远的那个字母的位置, 用于收割字符串, 直到字符串遍历完.

/**
 * @param {string} s
 * @return {number[]}
 */
var partitionLabels = function (s) {
  const n = s.length
  const result = []

  // 存储字母出现的最远的位置
  const maxPositionMap = new Map()
  for (let i = 0; i < n; i++) {
    maxPositionMap.set(s[i], i)
  }

  let start = 0 // 待切割的起始位置
  let maxPosition = 0 // 当前字母出现的最远位置
  for (let i = 0; i < n; i++) {
    maxPosition = Math.max(maxPosition, maxPositionMap.get(s[i]))

    // 正好扫描到"已扫描字符的最远位置"时, 收割字符串
    if (maxPosition === i) {
      result.push(i - start + 1)
      start = i + 1 // 更新 start 至下一个待切割字符串的起点
    }
  }

  return result
}