763. Partition Labels

📝 Problem Details

• Title: 763. Partition Labels
• Link: https://leetcode.com/problems/partition-labels/
• Difficulty: Medium
• Tags/Categories: Greedy Hashmap

input string s partition the string into as many parts as possible each letter appears in at most one part cant change the order of the string

💭What Were My Initial Thoughts?

- since each letter appears in at most one part, we need to ensure that all occurences of a letter are in a single contiguous substring
- greedy: we should extend the current partition if we encounter a letter that already appeared earlier 
- the goal is to make the smallest partition possible while ensuring that every character in a partition does not appear outside of it 

💡 Explanation of Solution

1. precompute last occurrences
	- create a hashmap (lastOCcurrence) storing the last index where each character appears in `s`

2. traverse the string greedily
	- keep extending the current position until we reach the last occurrence of every character inside it
	- when we reach the farthest known last occurrence, we finalise the partition and start a new one 

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1) since we would have a max of 26 values in our hashmap

💻 Implementation of Solution

class Solution {
public:
    vector<int> partitionLabels(string s) {
        unordered_map<char, int> lastOccurrence;
 
        // store last occurrences index of each character in the string
        for(int i=0; i < s.size(); i++) {
            lastOccurrence[s[i]] = i;
        }
 
        vector<int>partitions;
        int maxLast = 0;
        int start = 0;
 
        // traverse and create partitions
        for(int i=0; i < s.size(); i++) {
            maxLast = max(maxLast, lastOccurrence[s[i]]);
 
            // if we reach the farthest last occurrence of the char
            // finalise the partition
            if(i == maxLast) { 
                partitions.push_back(i - start + 1);
                start = i + 1;
            }
        }
 
        return partitions;
    }
};