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; } };
