HHot 100C++ 图解

763. 划分字母区间

一句话套路记录每个字母末次位置 + 区间合并

题目描述

给你一个字符串 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 仅由小写英文字母组成

思路

时间O(n + Σ)
空间O(Σ)

思路

先记录每个字母的最后出现位置 last[c]。

从左往右扫,维护「当前片段必须延伸到的右端点」end = max(end, last[c]);

一旦 i == end,说明这个片段里的字母都不会再出现,可以切断。

本质是「区间合并」:每个字母给出一个必须在一起的区间 [i, last],求合并后的长度。

图解

a 0 b 1 a 2 b 3 c 4 b 5 a 6 c 7 a 8 d 9 e 10 f 11 e 12 g 13 d 14 e 15 h 16 i 17 j 18 h 19 k 20 l 21 i 22 j 23
字符串 ababcbacadefegdehijhklij(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/14_greedy.cpp19 行
namespace lc0763 {
class Solution {
 public:
  vector<int> partitionLabels(const string& s) {
    vector<int> last(26, -1);
    for (int i = 0; i < (int)s.size(); ++i) last[s[i] - 'a'] = i;
    vector<int> ans;
    int start = 0, end = 0;
    for (int i = 0; i < (int)s.size(); ++i) {
      end = max(end, last[s[i] - 'a']);  // 想把这段留在身后,就得至少延伸到 end
      if (i == end) {
        ans.push_back(i - start + 1);
        start = i + 1;
      }
    }
    return ans;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q763_partition_labels6 行
lc0763::Solution s;
CHECK_EQ(s.partitionLabels("ababcbacadefegdehijhklij"), vector<int>{9, 7, 8});
CHECK_EQ(s.partitionLabels("eccbbbbdec"), vector<int>{10});
CHECK_EQ(s.partitionLabels("abc"), vector<int>{1, 1, 1});
CHECK_EQ(s.partitionLabels("aa"), vector<int>{2});
CHECK_EQ(s.partitionLabels("abac"), vector<int>{3, 1});

↑↓ 选择↵ 打开/ 随时唤起