Algorithm Day81 - Partition Labels

🧩 Problem Description

A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

---

💬 Example

Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
Each letter appears in at most one part.

---

💡 Intuition

We want to cut the string into maximum number of parts such that no character appears in more than one part.
Key idea: for each character, precompute its last occurrence index. Then scan the string and maintain a running end which is the farthest last occurrence of characters seen so far. When the current index reaches end, we can close a partition (from previous cut to end) and start a new one.

This is a greedy strategy: always close a partition as soon as every character inside it cannot appear later.

---

🔢 Java Code (Greedy)

import java.util.*;

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

---

⏱ Complexity Analysis

• Time: O(n) — one pass to compute last positions and one pass to partition.
• Space: O(1) (excluding output) — fixed-size array of 26 for lowercase letters.

---

✍️ Summary

• Precompute each character’s last occurrence.
• Scan and extend the current partition’s end to cover all last occurrences of letters seen.
• When current index equals the partition end, emit partition size and start a new one.

Related problems

• lc-763 variations with different alphabets or constraints