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 <= 500s仅由小写英文字母组成
思路
时间
O(n + Σ)空间
O(Σ)思路
先记录每个字母的最后出现位置 last[c]。
从左往右扫,维护「当前片段必须延伸到的右端点」end = max(end, last[c]);
一旦 i == end,说明这个片段里的字母都不会再出现,可以切断。
本质是「区间合并」:每个字母给出一个必须在一起的区间 [i, last],求合并后的长度。
图解
字符串
ababcbacadefegdehijhklij(来自本仓库测试数据,下标从 0 开始)逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
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;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
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});