763. 划分字母区间
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。
思路
可以统计字符串中每个字符的最后出现位置，然后使用双指针start和end从字符串头开始，由于同一字母只能出现在其中一个片段，所以end = max（end， index[S[i] - ‘a’]），当遍历的位置到达end时，说明可以划分为一个片段，更新start = end + 1，开始后续划分。
代码
class Solution {
public:
vector
<int> partitionLabels(string S
) {
int size
= S
.size();
int index
[26];
for(int i
= 0; i
< size
; i
++) {
index
[S
[i
] - 'a'] = i
;
}
vector
<int> ans
;
int start
= 0, end
= 0;
for(int i
= 0; i
< size
; i
++) {
end
= max(end
, index
[S
[i
] - 'a']);
if(i
== end
) {
ans
.push_back(end
- start
+ 1);
start
= end
+ 1;
}
}
return ans
;
}
};
