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 = max(end, last[s[i] - 'a']);

            //step 3:cut partition
            if(i == end) {
                res.push_back(end - start + 1);
                start = i + 1;
            }
        }

        return res;
    }
};

Example

Input: -> "ababcbacadefegdehijhklij"

Output: -> [9, 7, 8]

How to Think

1. Treat it like a window
2. Expand until all characters are “safe”
3. When no future dependency -> cut

Complexity

Time: O(n)
Space: O(1) (26 characters only)

What I Learned

• Not all problems are pure two-pointer
• This is more like greedy + window expansion
• Tracking last occurrence is the key trick