763. Partition Labels.cpp

/**
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:

S will have length in range [1, 500].
S will consist of lowercase letters ('a' to 'z') only.
**/

//Your runtime beats 7.00 % of cpp submissions.
/**
class Solution {
public:
    bool isIntersect(vector<char>::iterator s1b, vector<char>::iterator s1e, vector<char>::iterator s2b, vector<char>::iterator s2e){
        //adapted from https://stackoverflow.com/questions/2404094/how-do-i-get-characters-common-to-two-vectors-in-c
        for (std::vector<char>::iterator i = s1b; i != s1e; ++i){
            if (std::find(s2b, s2e, *i) != s2e){
                return true;
            }
        }
        return false;
    }
    
    vector<int> partitionLabels(string S) {
        vector<char> vecS(S.begin(), S.end());
        // copy(vecS.begin(), vecS.end(), std::ostream_iterator<char>(std::cout, " "));
        vector<int> result;
        
        int start = 0;
        int cur = 1;
        vector<char> intersection(S.size());
        
        while(cur < S.size()){
            if(!isIntersect(vecS.begin()+start, vecS.begin()+cur, vecS.begin()+cur, vecS.end())){
                //if two set are disjoint, split here
                result.push_back(cur-start); //the length of this segment
                start = cur; //start from cur next time
            }
            cur++;
        }
        result.push_back(cur-start);
        return result;
    }
};
**/

//Your runtime beats 39.62 % of cpp submissions.
/**
Approach #1: Greedy [Accepted]
Intuition

Let's try to repeatedly choose the smallest left-justified partition. Consider the first label, say it's 'a'. The first partition must include it, and also the last occurrence of 'a'. However, between those two occurrences of 'a', there could be other labels that make the minimum size of this partition bigger. For example, in "abccaddbeffe", the minimum first partition is "abccaddb". This gives us the idea for the algorithm: For each letter encountered, process the last occurrence of that letter, extending the current partition [anchor, j] appropriately.

Algorithm

We need an array last[char] -> index of S where char occurs last. Then, let anchor and j be the start and end of the current partition. If we are at a label that occurs last at some index after j, we'll extend the partition j = last[c]. If we are at the end of the partition (i == j) then we'll append a partition size to our answer, and set the start of our new partition to i+1.

Complexity Analysis

Time Complexity: O(N), where N is the length of S.

Space Complexity: O(N).
**/
class Solution {
public:
    vector<int> partitionLabels(string S) {
        int last[26];
        for (int i = 0; i < S.length(); ++i)
            last[S[i] - 'a'] = i;
        
        int j = 0, anchor = 0;
        vector<int> ans;
        for (int i = 0; i < S.length(); ++i) {
            j = max(j, last[S[i] - 'a']); //push the boundary of this segment to the right
            if (i == j) { //if we are now at the supposed boundary of this segment, split here
                ans.push_back(i - anchor + 1);
                anchor = i + 1; //start from here next time
            }
        }
        return ans;
    }
};