力扣 划分字母区间

题目：

给你一个字符串s。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串"ababcc"能够被分为["abab", "cc"]，但类似["aba", "bcc"]或["ab", "ab", "cc"]的划分是非法的。

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

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

解答：

1️⃣ 问题本质

题目要求把字符串划分成若干连续区间，使得：

每个字母只出现在其中一个区间内

并返回每个区间的长度。

2️⃣ 关键观察

如果某个字母在字符串中最右一次出现的位置是pos，
那么只要当前区间里包含了这个字母，这个区间最少要延伸到pos。

➡️区间的右边界由区间内所有字符的“最后出现位置”的最大值决定

3️⃣ 预处理（核心准备）

先遍历一次字符串，记录：

• 每个字母最后一次出现的下标

这样后续在遍历时，可以随时知道：

“当前字符最远会把区间拉到哪里”。

4️⃣ 贪心划分区间（核心思想）

从左到右遍历字符串：

• 维护一个变量right：
  表示当前区间必须到达的最右边界

• 每遇到一个字符：

  • 更新right为当前right和该字符最后出现位置的最大值

• 当遍历位置i == right时：

  • 说明当前区间内的所有字符都不会再出现在后面

  • 可以安全地切分一个区间

  • 记录区间长度

  • 从下一个位置开始新一段

这是一个一次扫描 + 局部最优即全局最优的贪心过程。

class Solution { public: vector<int> partitionLabels(string s) { int last[26]; vector<int> length; for (int i = 0; i < s.size(); i++) last[s[i] - 'a'] = i; int right = -1; int start = 0; for (int i = 0; i < s.size(); i++) { right = max(right, last[s[i] - 'a']); if (i == right) { length.push_back(i - start + 1); start = i + 1; } } return length; } };