Fork me on GitHub

Partition Labels

Posted on

Description

https://leetcode.com/problems/partition-labels/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    vector<int> partitionLabels(string S) {
        vector<pair<int, int>> pairVector;
        vector<int> position(26, -1); //The mapping between character to interval index
        int index = 0;
        while (index < S.size()) {
            if(position[S[index]-'a'] == -1) {
                position[S[index]-'a'] = pairVector.size();
                pairVector.push_back(make_pair(index, index));
            } else {
                int startIndex = position[S[index]-'a']; //The starting index to merge
                pairVector[startIndex].second = index;
                if (startIndex < pairVector.size()-1) {
                    for (int i = pairVector[startIndex + 1].first; i <= pairVector[pairVector.size()-1].second; ++i) {
                        position[S[i]-'a'] = startIndex;
                    }
                }
                
                pairVector.resize(startIndex + 1);
            }
            ++index;
        }
        vector<int> ret;
        for (auto& item : pairVector) {
            cout << item.first << item.second << endl;
            ret.push_back(item.second - item.first + 1);
        }
        return ret;
    }
};