Partition Labels

medium hash map two pointers string greedy

Problem

Partition string s into as many parts as possible so each letter appears in at most one part. Return the list of part sizes (in order).

Inputs = "ababcbacadefegdehijhklij"

Output[9, 7, 8]

Parts "ababcbaca" | "defegde" | "hijhklij" all keep their letters self-contained.

def partition_labels(s):
    last = {c: i for i, c in enumerate(s)}
    out = []
    start = end = 0
    for i, c in enumerate(s):
        end = max(end, last[c])
        if i == end:
            out.append(i - start + 1)
            start = i + 1
    return out

function partitionLabels(s) {
  const last = {};
  for (let i = 0; i < s.length; i++) last[s[i]] = i;
  const out = [];
  let start = 0, end = 0;
  for (let i = 0; i < s.length; i++) {
    end = Math.max(end, last[s[i]]);
    if (i === end) { out.push(i - start + 1); start = i + 1; }
  }
  return out;
}

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] last = new int[26];
        for (int i = 0; i < s.length(); i++) last[s.charAt(i) - 'a'] = i;
        List<Integer> out = new ArrayList<>();
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, last[s.charAt(i) - 'a']);
            if (i == end) { out.add(i - start + 1); start = i + 1; }
        }
        return out;
    }
}

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> last(26, 0);
        for (int i = 0; i < (int)s.size(); i++) last[s[i] - 'a'] = i;
        vector<int> out;
        int start = 0, end = 0;
        for (int i = 0; i < (int)s.size(); i++) {
            end = max(end, last[s[i] - 'a']);
            if (i == end) { out.push_back(i - start + 1); start = i + 1; }
        }
        return out;
    }
};

Explanation

We want to cut the string into as many pieces as possible so that no letter appears in two different pieces. The key insight is that a piece can only end once we have passed the last occurrence of every letter we have seen so far.

So first we make one pass to record, for each letter, the last index where it appears, stored in last. This tells us how far each letter forces the current piece to stretch.

Then we scan left to right with a running end, the farthest last-index among letters seen in the current piece: end = max(end, last[c]). The moment our position i reaches end, every letter inside is fully contained, so we cut here, record the length i - start + 1, and start a new piece.

This is a greedy strategy: we always close a piece at the earliest legal spot, which maximizes the number of pieces.

Example: in "ababcbacadefegde...", while scanning the first part, 'a' last appears at index 8, so end gets pulled to 8. Only when i hits 8 do we cut, giving a first piece of length 9.

Time: O(n) Space: O(1)