力扣 hot100 Day72

763. 划分字母区间

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

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

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

class Solution {
public:vector<int> partitionLabels(string s) {unordered_map <char,int> record;for(int i =0;i<s.length();i++){if(i>record[i]){record[s[i]]=i;}}vector<int>result;int start = 0;int maxn=0;for(int i=0;i<s.length();i++){maxn=max(maxn,record[s[i]]);if(i == maxn) {result.push_back(i - start + 1);start = i + 1;}}return result;}
};

第一次循环，先记录每个字母最后的位置，存在哈希表中。

第二次循环，维护一个区间，记录区间中所有字母最后位置的最大值，当i等于这个最大值时，就可以推入结果容器了。

核心目标就是，确保每个区间所有元素的末位置都包含在区间内