763: Partition-Labels
Medium

table of contents

This is basically just a interval partitioning question in disguise.

If you look at it closely, you basically have a maximum of 26 intervals; 1 interval spanning between the first and last instance of each respective letter. Then, once we have each interval, we can just merge the overlapping ones and then simply append the length of each merged interval to the ans array.

code

class Solution {
public:
    vector<int> partitionLabels(string s) {
        // storing the start & end index of each letter of the alphabet
        vector<pair<int, int>> alphabet (26, {INT32_MAX, INT32_MAX});
        for (int i = 0; i < s.size(); ++i) {
            alphabet[s[i]-'a'].first = min(alphabet[s[i]-'a'].first, i);
            alphabet[s[i]-'a'].second = i;
        }

        // order the starting and ending index of each letter
        vector<pair<int, char>> letterIndex;
        for (int i = 0; i < 26; ++i) {
            if (alphabet[i].second != INT32_MAX) {
                letterIndex.push_back({alphabet[i].first, i});
                letterIndex.push_back({alphabet[i].second, i});
            }
        }
        sort(letterIndex.begin(), letterIndex.end());

        // to track whether we have seen the letter or not 
        vector<int> seenAlphabet (26, 0);

        // to track the number of intervals we are inside of
        int counter = 0;
        // to track when the previous interval ennded
        int previous_partition = -1;
        int current_index = 0;
        vector<int> ans;
        for (int i = 0; i < letterIndex.size(); ++i) {
            seenAlphabet[letterIndex[i].second] ^= 1;
            // we will only see each letter twice;
            // first XOR operation == 1
            // second XOR operation == 0
            if (seenAlphabet[letterIndex[i].second]) {
                ++counter;
            } else {
                --counter;
            }
            current_index = letterIndex[i].first;
            if (counter == 0) {
                ans.push_back(current_index - previous_partition);
                previous_partition = current_index;
            }
        }
        return ans;
    }
};

complexity