763. 划分字母区间
难度中等305
字符串
S由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。
示例 1：
输入：S = "ababcbacadefegdehijhklij" 输出：[9,7,8] 解释： 划分结果为 "ababcbaca", "defegde", "hijhklij"。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
class Solution {
public:vector<int> partitionLabels(string S) {vector<int> res;if(S.empty()) return res;int n = S.size();unordered_map<char, int> hash;//得到每个字符出现的最后的下标for(int i = 0; i < n; i ++) {hash[S[i]] = i; }int start = 0, end = 0;for(int i = 0; i < n; i ++) {//每次更新片段的最远位置end = max(end, hash[S[i]]);// 当i == end时，意味着这个片段已经遍历完if(i == end) { res.push_back(end- start + 1);start = end + 1;}}return res;}
};