分析:运用滑动窗口的思想,开needs哈希表和窗口哈希表,由于要划分尽可能多的片段,那么只要当前窗口中全部元素都满足了needs的数量(同一字母只在一个片段中),就立即断开,保证尽可能多的数量
class Solution {
public:
vector<int> partitionLabels(string s) {
unordered_map<char,int> needs;//需求
unordered_map<char,int> mp; //窗口
int valid=0; //满足条件的数量
int j=0,i=0;
for(char c:s)
needs[c]++;
vector<int> q;
//j表示片段左端点,i表示片段右端点
for(int i=0,j=0;i<s.size();i++)
{
char c=s[i];
mp[c]++;
if(mp[c]==needs[c]) //同一字母在一个片段
valid++;
if(valid==mp.size())//窗口中所有元素都满足同一字母再一个片段
{
q.push_back(i-j+1);
valid=0; //清空
mp.clear();
j=i+1;
}
}
return q;
}
};