题目链接
题目描述
字符串 S 由小写字母组成。
把这个字符串划分为尽可能多的片段,
同一字母最多出现在一个片段中。
返回一个表示每个字符串片段的长度的列表。
要求
时间复杂度:O(n)
思路
-
先遍历一遍 s ,用 map 记录每一个字母出现的区间。
问题就转化成了对区间的合并操作。 -
再遍历一遍 s ,一边遍历,一边处理当前字符所出现的区间。
若区间有重叠,直接合并,
若无重叠,更新答案。
C++代码
class Solution {
public:
vector<int> partitionLabels(string s) {
vector<int> ans;
unordered_map<char, pair<int, int>> mp;
int len = s.length();
for (int i = 0; i < len; i++) {
if (mp.count(s[i]) == 0)
mp[s[i]].first = mp[s[i]].second = i;
else
mp[s[i]].second = i;
}
int L= 0, R = 0;
for (int i = 0; i < len; i++) {
if (mp[s[i]].first > R) {
ans.push_back(R-L+1);
L = i;
R = mp[s[i]].second;
} else if (mp[s[i]].second > R) {
R = mp[s[i]].second;
}
}
ans.push_back(R-L+1);
return ans;
}
};