[leetcode-763] Partition Labels

Description
A string S of lowercase English 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.
Solution

Select a partition with the first and last occurrence of a letter, mark them as start and end of a list respectively.

Iterate all letters within the list.

If found letter have last occurrence bigger than end, update the end accordingly.

If end was reached, update count with end-start+1

Start new round with end + 1

code:

class Solution {
     
public:
    vector<int> partitionLabels(string S) {
     
        vector<int> result;
        int lastOccurence[26];
        
        for(int i = 0; i < S.length(); i++) {
     
            lastOccurence[S[i] - 'a'] = i;
        }
        
        int i = 0;
        while(i < S.length()) {
     
            int end = lastOccurence[S[i] - 'a'];
            
            int j = i;
            
            while(j<end) {
     
                end = max(end, lastOccurence[S[j] - 'a']);
                j++;
            }
            
            int count = j - i + 1;
            result.push_back(count);
            
            i = j + 1;
        }
        
        return result;
        
    }
};