763. 划分字母区间

给你一个字符串s。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串"ababcc"能够被分为["abab", "cc"]，但类似["aba", "bcc"]或["ab", "ab", "cc"]的划分是非法的。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是s。

返回一个表示每个字符串片段的长度的列表。

示例 1：

输入：s = "ababcbacadefegdehijhklij"输出：[9,7,8]解释：划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

示例 2：

输入：s = "eccbbbbdec"输出：[10]

提示：

• 1 <= s.length <= 500
• s仅由小写英文字母组成

class Solution { public: vector<int> partitionLabels(string s) { vector<vector<int>> nums(26, vector<int>()); for(int i=0; i<s.length(); ++i){ if(!nums[s[i] - 'a'].size()){ nums[s[i] - 'a'].push_back(i); nums[s[i] - 'a'].push_back(i); } else{ nums[s[i] - 'a'][1] = i; } } nums.erase(remove_if(nums.begin(), nums.end(), [](vector<int>& row){return row.empty();}), nums.end()); sort(nums.begin(), nums.end(), [](vector<int> a, vector<int> b){ return a[0] < b[0];}); vector<int> res; int k=nums[0][1], prev = 0; for(int i=1; i<nums.size(); ++i){ if(k < nums[i][0]){ int cur = k + 1 - prev; prev = k + 1; res.push_back(cur); } k = max(nums[i][1], k); } res.push_back(k + 1 - prev); return res; } };