763. 划分字母区间
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
示例：
输入：S = "ababcbacadefegdehijhklij" 输出：[9,7,8]
解释：
划分结果为 “ababcbaca”, “defegde”, “hijhklij”。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。
解题思路
用 last[字母] 记录每个字母最后的位置，遍历第一个找第一个对应的字母最后出现的位置，再把start end向后移动为下一个字母，以此类推
代码
class Solution { public: vector<int> partitionLabels(string S) { int last[26]; int size=S.size(); for(int i=0;i<size;i++) { // 记录每个字母最后的位置 last[S[i] - 'a'] = i; } vector<int> part; int start=0,end=0; for (int i = 0; i < size; i++) { // 每次初始化end 使得作用到新的区间中 end=max(end,last[S[i]-'a']); // 如果遍历到，第一个字母的最后一个 让该长度写入容器 并且让 start = 新的字母位置 if (i == end) { part.push_back(end - start + 1); start = end + 1; } } return part; } };
