给你一个字符串s。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。例如字符串ababcc能够被分为[abab, cc]但类似[aba, bcc]或[ab, ab, cc]的划分是非法的。注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是s。返回一个表示每个字符串片段的长度的列表。这道题的核心是把字符串问题转化为区间合并问题。每个字母在字符串中可能出现多次为了保证同一字母最多出现在一个片段中每个字母的第一次出现位置和最后一次出现位置必须被划分在同一个片段里。整个过程可以分为三步第一步遍历字符串记录每个字母最后一次出现的位置。比如对于字符串 ababcbacadefegdehijhklij字母 a 最后一次出现在索引8b 最后一次出现在索引5c 最后一次出现在索引7。第二步再次遍历字符串维护两个变量start 表示当前片段的起始位置end 表示当前片段的最远边界。每遍历到一个字符就用这个字符的最后出现位置更新 end取最大值。第三步当遍历到索引 i 等于 end 时说明当前片段内的所有字母都不会出现在 i 之后可以在此处切割。将 end - start 1 加入结果数组然后将 start 更新为 i 1继续寻找下一个片段。代码如下class Solution { public: vectorint partitionLabels(string s) { int ns.size(); int last[26]; for(int i0;in;i){ last[s[i]-a]i; } vectorintans; int start0,end0; for(int i0;in;i){ endmax(end,last[s[i]-a]); if(endi){ ans.push_back(end-start1); startend1; } } return ans; } };
给你一个字符串s。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。例如字符串ababcc能够被分为[abab, cc]但类似[aba, bcc]或[ab, ab, cc]的划分是非法的。注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是s。返回一个表示每个字符串片段的长度的列表。这道题的核心是把字符串问题转化为区间合并问题。每个字母在字符串中可能出现多次为了保证同一字母最多出现在一个片段中每个字母的第一次出现位置和最后一次出现位置必须被划分在同一个片段里。整个过程可以分为三步第一步遍历字符串记录每个字母最后一次出现的位置。比如对于字符串 ababcbacadefegdehijhklij字母 a 最后一次出现在索引8b 最后一次出现在索引5c 最后一次出现在索引7。第二步再次遍历字符串维护两个变量start 表示当前片段的起始位置end 表示当前片段的最远边界。每遍历到一个字符就用这个字符的最后出现位置更新 end取最大值。第三步当遍历到索引 i 等于 end 时说明当前片段内的所有字母都不会出现在 i 之后可以在此处切割。将 end - start 1 加入结果数组然后将 start 更新为 i 1继续寻找下一个片段。代码如下class Solution { public: vectorint partitionLabels(string s) { int ns.size(); int last[26]; for(int i0;in;i){ last[s[i]-a]i; } vectorintans; int start0,end0; for(int i0;in;i){ endmax(end,last[s[i]-a]); if(endi){ ans.push_back(end-start1); startend1; } } return ans; } };
