划分字母区间

更新: 7/4/2026 字数: 0 字 时长: 0 分钟

题目描述

给你一个字符串 s。我们要把它划分成尽可能多的片段，使得同一个字母最多只出现在其中一个片段里。返回一个表示每个片段长度的整数列表。

示例：

输入：s = "ababcbacadefegdehijhklij"
输出：[9, 7, 8]
解释：
  划分结果为 "ababcbaca" | "defegde" | "hijhklij"
  像 "ababcbaca" 里 a、b、c 都不会再出现在后面的片段中；
  若把它拆成 "ababcbaca" 和 "defegde" 之外更细的段，
  就会让某个字母横跨两段，不满足要求。

思路拆解

先想清楚约束：一个字母要么全在一段，要么不在

关键约束是「同一字母只能属于一个片段」。这意味着：只要某个字母出现在当前片段里，那么它最后一次出现的位置之前的所有字符，都必须和它待在同一段。否则那个字母就会横跨两段。

点击展开暴力解法（区间合并思路，O(n) 但更繁琐）

可以把每个字母看成一个区间 [first, last]（第一次到最后一次出现的下标），然后做区间合并：能重叠的区间必须并进同一片段。合并完，每个合并后的大区间就是一段。

function partitionLabels(s) {
  const first = {}, last = {}
  for (let i = 0; i < s.length; i++) {
    if (first[s[i]] === undefined) first[s[i]] = i
    last[s[i]] = i
  }
  // 收集所有字母区间并按左端点排序
  const intervals = Object.keys(first)
    .map(c => [first[c], last[c]])
    .sort((a, b) => a[0] - b[0])
  const res = []
  let [ls, le] = intervals[0]
  for (let k = 1; k < intervals.length; k++) {
    const [cs, ce] = intervals[k]
    if (cs <= le) le = Math.max(le, ce) // 重叠，合并
    else { res.push(le - ls + 1); [ls, le] = [cs, ce] }
  }
  res.push(le - ls + 1)
  return res
}

这个做法正确，但需要额外排序和区间数组，写起来啰嗦。下面的贪心解法更简洁优雅。

最优解：记录「最后出现位置」+ 贪心扩展边界

我们其实不需要显式合并区间。换个角度：从左往右扫描时，为当前片段维护一个「必须延伸到的最远边界 end」。 每遇到一个字符 c，就用它最后出现的位置去更新这个边界：

当扫描指针 i 恰好走到 end 时，说明从片段起点到 i 之间出现过的所有字母，最后一次出现都不超过 i——它们不会再出现在后面。此刻就可以安全地切一刀。

核心思路

两遍扫描即可：

1. 预处理：用一次遍历记录每个字母最后一次出现的下标 last[c]。
2. 贪心划分：再扫一遍，维护当前片段的最远边界 end = max(end, last[s[i]])；一旦 i === end，就在此切割，记录长度 i - start + 1，并把下一段起点移到 i + 1。

因为每次都让片段「尽可能早地结束」（一碰到边界就切），所以得到的片段数最多。

一步步看下面的动画

下面的动画用样例 s = "ababcbacadefegdehijhklij" 演示贪心过程：蓝色是扫描指针 i，红色描边是当前片段的最远边界 end，i 追上 end 时画绿色切割线，已确定的片段按段号着色。可以单步、自动播放或重置。

贪心 · 划分字母区间演示

样例：s = "ababcbacadefegdehijhklij"，答案 [9, 7, 8]

当前阶段：准备

每个字母最后出现的下标 last：

a → 8b → 5c → 7d → 14e → 15f → 11g → 13h → 19i → 22j → 23k → 20l → 21

a0

b1

a2

b3

c4

b5

a6

c7

a8

d9

e10

f11

e12

g13

d14

e15

h16

i17

j18

h19

k20

l21

i22

j23

已切出片段：暂无

扫描指针 i当前边界 end当前片段范围已确定片段

目标：把字符串划分成尽可能多的片段，使同一个字母只出现在一个片段里，返回每段长度。

步骤 0 / 29

完整代码

/**
 * 划分字母区间：记录每个字母最后出现位置 + 贪心扩展边界。
 */
function partitionLabels(s) {
  // 第一步：记录每个字母最后一次出现的下标
  const last = {}
  for (let i = 0; i < s.length; i++) {
    last[s[i]] = i
  }

  const res = []
  let start = 0   // 当前片段的起点
  let end = 0     // 当前片段必须延伸到的最远边界

  for (let i = 0; i < s.length; i++) {
    // 用当前字符的最后出现位置扩展边界
    end = Math.max(end, last[s[i]])
    // 扫描指针追上边界 → 当前片段可以结束
    if (i === end) {
      res.push(i - start + 1)  // 记录片段长度
      start = i + 1            // 下一段从 i+1 开始
    }
  }

  return res
}

// 示例
console.log(partitionLabels("ababcbacadefegdehijhklij")) // [9, 7, 8]

易错点

• 判断切割用的是 i === end，不是 i === last[s[i]]——边界 end 会被片段内所有字母共同撑大，只看当前字母会切错。
• end 一旦被某个字母撑大，就不能缩小；Math.max 保证它单调不减。
• 片段长度是 i - start + 1（闭区间含两端），别漏掉 +1。
• 切割后必须把 start 更新为 i + 1，否则下一段长度会算错。

复杂度分析

解法	时间复杂度	空间复杂度	说明
区间合并			为不同字母数，需排序
最后位置 + 贪心			两趟线性扫描，最简洁

其中 是字符串长度， 是不同字母的个数（如仅小写字母则 ，空间可视为 ）。

边界与易错点

• 空串或单字符： s = "" 返回 []；s = "a" 返回 [1]，循环第一步 i === end === 0 即切割。
• 所有字符相同： 如 "aaaa"，end 一路被撑到末尾，最后只切出一段 [4]。
• 全部字符互不相同： 如 "abcd"，每一步 i === end 都成立，切成 [1,1,1,1]——片段数达到最多。
• 字符集不止小写字母： 用哈希表 last 存下标即可自适应任意字符集，无需假设 26 个字母。
• 不要用 first/last 双端做复杂判断： 贪心解法只需要 last，比区间合并更省心，也不易写错。