Partition Labels

Leetcode Problem:

• Partition Labels

Summary

• Partitioning a string into parts where each letter appears in at most one part

Approach

• Use a hashmap to store the last index of each character, then iterate through the string, updating the end index and adding the current part size to the result vector when the end index matches the current index

Complexity

• O(n) where n is the length of the string

Explanation

• The approach is to first store the last index of each character in a hashmap
• Then, we iterate through the string, updating the end index whenever we encounter a character
• When the end index matches the current index, we know we've reached the end of the current part, so we add its size to the result vector and reset the start and end indices
• This way, we ensure that each letter appears in at most one part and that the resultant string is the original input string

Solution Code:

class Solution {
public:
    int lastIdx[256];
    vector partitionLabels(string s) {
        for(int i = 0 ; i < s.size(); i++){
            lastIdx[s[i]] = i;
        }

        vector ans;
        int start = 0;
        int end = 0;
        for(int i = 0 ; i < s.size(); i++){
            end = max(end, lastIdx[s[i]]);
            if(end == i){
                ans.push_back(end - start + 1);
                start = end = end +1;
            }
        }
        return ans;
    }
};