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 ()