768. Partition Labels

• Difficulty: Medium

• Topics: Two Pointers, Greedy

• Similar Questions:

  • Merge Intervals

Problem:

A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:

Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.

Note:

Solutions:

class Solution {
public:
    vector<int> partitionLabels(string S) {
        int charLastIndex[26];
        for (int i = 0; i < 26; ++i) {
            charLastIndex[i] = -1;
        }

        for (int i = 0; i < S.length(); ++i) {
            charLastIndex[S[i] - 'a'] = i;
        }

        vector<int> ret;
        int left = 0;
        int right = 0;

        for (int i = 0; i < S.length(); ++i) {
            right = max(right, charLastIndex[S[i] - 'a']);
            if (i != right) {
              continue;  
            }

            ret.push_back(right - left + 1);
            left = right + 1;
            right = left;
        }

        return ret;
    }
};