Partition Labels

Cut a string into as many parts as possible so each letter appears in only one part, using each letter's last occurrence.

The idea

Each letter spans an interval from its first to its last occurrence, and a part must contain the whole span of every letter in it. So this is merging intervals in disguise: walk the string, stretch the current part's end to the last occurrence of every letter you meet, and when i reaches that end, nothing inside the part appears later - cut there.

Code

public static List<int> PartitionLabels(string s) {
    var last = new int[26];
    for (int i = 0; i < s.Length; i++) last[s[i] - 'a'] = i;
    var sizes = new List<int>();
    int start = 0, end = 0;
    for (int i = 0; i < s.Length; i++) {
        end = Math.Max(end, last[s[i] - 'a']);
        if (i == end) { sizes.Add(end - start + 1); start = i + 1; }
    }
    return sizes;
}

Tips

• Cutting as soon as i == end gives the most parts: the part cannot end any earlier, and ending it later would only merge parts that do not need merging.
• The first pass is needed because the cut decision depends on letters that appear later in the string.
• last only needs 26 slots, so the extra space is O(1).

In the .NET library

s[i] - 'a' turns a lowercase char into 0..25 because char arithmetic in C# works on the UTF-16 code.