Partition Labels

LeetCode

第30天，一个月了。

今天的题目是Partition Labels:

这道题的解法如下：

先遍历一次字符串统计字符出现的次数保存在c1上，然后在遍历一次字符串，这次遍历时同样进行统计字符出现次数保存在c2上，并维护一个变量cnum，这个变量cnum表示当前出现过但是未出现完全的字符的种类数。当出现cnum为 0 时，就表示完成了一次划分。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> partitionLabels(string S) {
    vector<int> c1(26, 0);
    for(int i = 0, size = S.size(); i < size; i++) {
        c1[S[i] - 'a']++;
    }
    
    vector<int> c2(26, 0);
    vector<int> res;
    int temp = 1, cnum = 0;
    
    for(int i = 0, size = S.size(); i < size; i++, temp++) {
        int index = S[i] - 'a';
        if (c2[index] == 0) {
            cnum++;
        }
        if (++c2[index]== c1[index] && --cnum == 0) {
            res.push_back(temp); temp = 0;
        }
    }
    return res;
}