字符串S由小写字母组成. 我们要把这个字符串划分为尽可能多的片段, 同一字母最多出现在一个片段中. 返回一个表示每个字符串片段的长度的列表.
示例
输入: S = “ababcbacadefegdehijhklij”
输出: [9, 7, 8]
解释:
划分结果为"ababcbaca", “defegde”, “hijhklij”
每个字母最多出现在一个片段中. 像"ababcbacadefegde", “hijhklij” 的划分是错误的, 因为划分的片段较少.
提示
S的长度在[1, 500]之间S只包含小写字母a到z
题解
要尽可能多的划分片段, 划分的片段应该尽可能短. 满足子问题的解是局部最优的条件, 因此采用贪心解决. 一开始想法是统计每个字母的[开始, 结束]区间, 然后按照开始排序, 然后依次判断下一个字母的开始区间以及结束区间是否在当前区间片段内, 以此更新当前区间.
但是实际上不需要考虑字母第一次出现的位置, 因为假设当前片段是第一个划分的片段, 它一定是从[0]处开始的. 以这个位置作为片段的开端start, 并将当前字母最后一次出现的位置作为片段结尾end, 往后判断下一个字母最后一次出现的位置c_end, 如果这个字母最后一次出现的位置在[start, end]之间, 那么这个字母就属于当前片段. 反之, 如果大于end, 就更新end为c_end. 除非我们的i已经到达end这个位置, 就表示抵达当前片段的末尾了.
for(int i = 0; i < s.size(); i++) {
end = max(end, m_hash[s[i] - 'a'];
if(i == end) {
fragLength.pushback(end - start + 1);
start = end + 1;
}
}
