0763. 划分字母区间【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 贪心

1. 📝 题目描述

• leetcode

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

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

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

示例 1：

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

示例 2：

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

---

提示：

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

2. 🎯 s.1 - 贪心

c

int* partitionLabels(char* s, int* returnSize) {
    int last[26] = {0};
    int len = strlen(s);
    for (int i = 0; i < len; i++) last[s[i] - 'a'] = i;
    int* res = (int*)malloc(sizeof(int) * len);
    *returnSize = 0;
    int start = 0, end = 0;
    for (int i = 0; i < len; i++) {
        if (last[s[i] - 'a'] > end) end = last[s[i] - 'a'];
        if (i == end) {
            res[(*returnSize)++] = end - start + 1;
            start = end + 1;
        }
    }
    return res;
}

js

/**
 * @param {string} s
 * @return {number[]}
 */
var partitionLabels = function (s) {
  const last = new Array(26).fill(0)
  for (let i = 0; i < s.length; i++) last[s.charCodeAt(i) - 97] = i
  const res = []
  let start = 0,
    end = 0
  for (let i = 0; i < s.length; i++) {
    end = Math.max(end, last[s.charCodeAt(i) - 97])
    if (i === end) {
      res.push(end - start + 1)
      start = end + 1
    }
  }
  return res
}

py

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last = {c: i for i, c in enumerate(s)}
        res = []
        start = end = 0
        for i, c in enumerate(s):
            end = max(end, last[c])
            if i == end:
                res.append(end - start + 1)
                start = end + 1
        return res

• 时间复杂度：$O(n)$，其中 n 是字符串长度
• 空间复杂度：$O(1)$，字母表大小固定 26

算法思路：

• 先记录每个字母最后出现的位置
• 遍历时维护当前区间的右边界 end，不断更新为当前字母的最后位置
• 当遍历到 i == end 时，当前区间内所有字母均不会出现在后续区间，切割