Partition Labels – Greedy + Two Pointer Thinking

This problem looks confusing at first… “Split the string so each character appears in only one part” . But once you see the pattern, it becomes very clean. Key Idea Each character has a last occurrence in the string. -> If you know how far a character goes, you can decide where to cut the partition Approach (Simple Thinking) Step 1: Store last position of each character last[s[i] - 'a'] = i; Now you know: -> where each character must end Step 2: Traverse and expand partition Start from index 0 Keep updating end = farthest last occurrence seen so far end = max(end, last[s[i] - 'a']); Step 3: When i == end You found a valid partition store its length start a new partition Code (C++) class Solution { public: vector<int> partitionLabels(string s) { vector<int> last(26); //step 1:store last index for(int i = 0; i < s.size(); i++) { last[s[i] - 'a'] = i; } vector<int> res; int start = 0, end = 0; //step 2:expand window for(int i = 0; i < s.size(); i++) { end = m