You are given a string s.
Your task:

Partition the string into as many pieces as possible such that each letter appears in at most one partition.

Return a list containing the sizes of these partitions.

Example:

Input:  s = "ababcbacadefegdehijhklij"
Output: [9,7,8]

Explanation:
"ababcbaca" → all a,b,c contained
"defegde"  → all d,e,g contained
"hijhklij" → all h,i,j,k,l contained

Another example:

Input: "eccbbbbdec"
Output: [10]

---

Problem Understanding

Important characteristics:

• Each partition must fully contain all occurrences of the characters inside it.
• Once a character appears in a partition, it cannot appear later.
• We want the maximum number of partitions, meaning:
  • close partitions as soon as it’s safe
• The final result is the length of each partition, not the substrings themselves.

Key insight:

A partition ends when the farthest last occurrence of all characters inside it is reached.

---

Logic Explained in Simple English

Here’s the simplest way to reason about it:

1. First, scan the string and record the last index where each character appears.
2. Now iterate the string again, maintaining:
   • a running boundary (end) representing the farthest last occurrence seen so far
3. For each character:
   • update end to max(end, last occurrence of current character)
4. When the current index reaches end, it means:
   • all characters in this segment do not appear later
   • so we close the partition
   • record its size
   • start new partition after it

Why this works:

• We delay partition edges until guaranteed safe
• Ensures maximum number of partitions
• Greedy strategy works because decisions are locally optimal and globally valid

---

Step-by-Step Approach

1. Create array lastIndex[26]
2. Fill it with the last occurrence index of each character in s
3. Initialize:
   • start = 0
   • end = 0
4. Loop i from 0 to n-1:
   • update end = max(end, lastIndex[s[i]])
   • if i == end:
     • partition ends here
     • size = end – start + 1
     • add to result
     • set start = i + 1
5. Return result list

---

Java Implementation

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> result = new ArrayList<>();
        int start = 0;
        int end = 0;
        
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, last[s.charAt(i) - 'a']);
            
            if (i == end) {
                result.add(end - start + 1);
                start = i + 1;
            }
        }
        
        return result;
    }
}

---

Dry Run Example

Input:

"ababcbacadefegdehijhklij"

Compute last occurrences:

a:8, b:5, c:7, d:14, e:15, f:11, g:13, h:19,
i:22, j:23, k:20, l:21

Now iterate:

i=0 (‘a’): end=max(0,8)=8
i=1 (‘b’): end=max(8,5)=8
i=2 (‘a’): end=8
i=3 (‘b’): end=8
i=4 (‘c’): end=max(8,7)=8
i=5 (‘b’): end=8
i=6 (‘a’): end=8
i=7 (‘c’): end=8
i=8 reaches end → partition size = 8-0+1 = 9

start=9

Continue:

Second partition ends at 15 → size = 15-9+1 = 7
Third partition ends at 23 → size = 23-16+1 = 8

Final output:

[9,7,8]

---

Time and Space Complexity

Time Complexity

O(n)

One pass for last occurrences and one pass for partitioning.

Space Complexity

O(1)

Array of size 26, regardless of input length.

---

Common Mistakes and How to Avoid Them

Mistake 1: Trying to construct substring instead of sizes

Only lengths matter.

Mistake 2: Partitioning every time a character repeats

Must track farthest last occurrence.

Mistake 3: Overthinking with hash maps

26-character fixed alphabet allows simple array.

Mistake 4: Sorting characters or positions

Order in string must be preserved — no sorting.

Mistake 5: Using sets for active characters

Unnecessary — boundary tracking replaces it.