Problem Description

You are given a string s and need to partition it into as many parts as possible with a special constraint: each letter must appear in at most one part.

For example, given the string "ababcc":

• Valid partition: ["abab", "cc"] - letter 'a' only appears in the first part, 'b' only in the first part, and 'c' only in the second part
• Invalid partition: ["aba", "bcc"] - letter 'b' appears in both parts
• Invalid partition: ["ab", "ab", "cc"] - letters 'a' and 'b' appear in multiple parts

The key requirements are:

1. Each letter can only appear in one partition
2. You want to maximize the number of partitions (make each partition as small as possible)
3. The partitions must maintain the original order - when concatenated back together, they should form the original string s
4. Return a list of integers representing the size of each partition in order

For instance, if the string "ababcbacadefegdehijhklij" can be partitioned into ["ababcbaca", "defegde", "hijhklij"], the output would be [9, 7, 8] representing the lengths of each partition.

The challenge is to find where to make the cuts such that no letter crosses partition boundaries while creating as many partitions as possible.

Intuition

The key insight is that for each letter in the string, we need to know where it last appears. Why? Because once we include a letter in a partition, we must extend that partition at least until the last occurrence of that letter to ensure it doesn't appear in any other partition.

Think of it this way: if we see the letter 'a' at position 0, and 'a' also appears later at position 5, then our current partition must extend at least to position 5. But as we traverse from position 0 to 5, we might encounter other letters like 'b' or 'c' whose last occurrences are even further ahead - say position 8. This means our partition must now extend to position 8.

This suggests a greedy approach:

1. Start a new partition from the current position
2. As we traverse each character, keep track of the farthest position we must reach (based on the last occurrences of all characters we've seen so far)
3. Once we reach that farthest position, we can safely end the current partition there, knowing all characters in this partition won't appear anywhere else
4. Start a new partition from the next position

For example, with string "abaccb":

• 'a' appears last at position 2
• 'b' appears last at position 5
• 'c' appears last at position 4

Starting at position 0 ('a'), we know we must go at least to position 2. As we traverse:

• Position 0: 'a' requires going to position 2
• Position 1: 'b' requires going to position 5 (update our target)
• Position 2: 'a' requires position 2 (no change, still need position 5)
• Position 3: 'c' requires position 4 (no change, still need position 5)
• Position 4: 'c' requires position 4 (no change, still need position 5)
• Position 5: 'b' requires position 5 (we've reached our target!)

So the entire string forms one partition of size 6, since we can't split it without breaking the constraint.

Learn more about Greedy and Two Pointers patterns.

Solution Approach

The implementation follows the greedy approach identified in our intuition:

Step 1: Build a mapping of last occurrences

last = {c: i for i, c in enumerate(s)}

We create a dictionary where each character maps to its last occurrence index in the string. By iterating through the string with enumerate(s), each character's position gets updated, so we naturally end up with the last position for each character.

Step 2: Traverse and partition greedily We maintain three variables:

• mx: The farthest position we need to reach in the current partition (initially 0)
• j: The starting index of the current partition (initially 0)
• ans: List to store the sizes of each partition

for i, c in enumerate(s):
    mx = max(mx, last[c])
    if mx == i:
        ans.append(i - j + 1)
        j = i + 1

As we traverse each character at position i:

1. Update the farthest position: mx = max(mx, last[c])

   • For the current character c, check where it last appears (last[c])
   • Update mx to be the maximum of the current mx and this last occurrence
   • This ensures our partition extends far enough to include all occurrences of every character we've seen

2. Check if we can end the partition: if mx == i

   • When our current position i equals mx, it means we've reached the farthest position required for all characters in this partition
   • This is the optimal place to cut and start a new partition

3. Record the partition size: ans.append(i - j + 1)

   • The size of the current partition is from index j to index i inclusive
   • Length = i - j + 1

4. Start new partition: j = i + 1

   • Move the start of the next partition to the position right after the current partition ends

Time Complexity: O(n) where n is the length of the string - we traverse the string twice (once to build the last dictionary, once to partition)

Space Complexity: O(1) or O(26) for the last dictionary since there are at most 26 lowercase English letters

Example Walkthrough

Let's walk through the string "ababcbaca" step by step:

Step 1: Build the last occurrence map

• Traverse the string to find where each letter last appears:
  • 'a' appears at positions 0, 2, 6, 8 → last['a'] = 8
  • 'b' appears at positions 1, 3, 5 → last['b'] = 5
  • 'c' appears at positions 4, 7 → last['c'] = 7

So last = {'a': 8, 'b': 5, 'c': 7}

Step 2: Traverse and partition

Initialize: mx = 0, j = 0, ans = []

When we reach position 8:

• mx == i (both are 8), so we can end the partition here
• Partition size = i - j + 1 = 8 - 0 + 1 = 9
• Add 9 to ans: ans = [9]
• Update j = i + 1 = 9 (but we're done since i = 8 was the last character)

Result: [9] - The entire string forms one partition of size 9.

This makes sense because:

• 'a' appears throughout the string (positions 0, 2, 6, 8)
• We must include all occurrences of 'a' in the same partition
• Since 'a' appears at the very end (position 8), the entire string must be one partition

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. This is because:

• Building the last dictionary requires one pass through the string: O(n)
• The second loop iterates through the string once more: O(n)
• All operations inside the loop (max comparison, appending to list) are O(1)
• Total: O(n) + O(n) = O(n)

The space complexity is O(|Σ|), where |Σ| is the size of the character set. In this problem, since the input consists of lowercase English letters, |Σ| = 26. This is because:

• The last dictionary stores at most one entry for each unique character in the string, which is bounded by the size of the alphabet: O(|Σ|)
• The ans list stores the partition sizes, but in the worst case has at most n elements. However, this is not counted as extra space beyond the output
• Other variables (mx, j, i, c) use constant space: O(1)
• Total: O(|Σ|) = O(26) = O(1) for this specific problem with lowercase English letters

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Update the Maximum Last Index Continuously

A common mistake is to only check the last occurrence of the current character without maintaining the maximum across all characters seen so far in the current partition.

Incorrect approach:

for i, c in enumerate(s):
    # Wrong: Only considering current character's last occurrence
    if last[c] == i:
        ans.append(i - j + 1)
        j = i + 1

Why it fails: This would incorrectly partition when reaching a character's last occurrence, even if previous characters in the same partition extend further. For example, with "abba", it would incorrectly split after the first 'a' at index 0.

Correct approach:

for i, c in enumerate(s):
    # Continuously track the farthest position needed
    mx = max(mx, last[c])
    if mx == i:  # Only partition when we've covered all necessary positions
        ans.append(i - j + 1)
        j = i + 1

2. Off-by-One Error in Partition Size Calculation

Another frequent mistake is incorrectly calculating the partition size, often forgetting the inclusive nature of the boundaries.

Incorrect calculation:

ans.append(i - j)  # Wrong: Missing the +1

Correct calculation:

ans.append(i - j + 1)  # Correct: Inclusive of both start and end positions

For a partition from index 2 to index 5, the size should be 4 (indices 2, 3, 4, 5), which is 5 - 2 + 1 = 4, not 5 - 2 = 3.

3. Not Resetting the Partition Start Correctly

Incorrect reset:

j = i  # Wrong: Would overlap with previous partition

Correct reset:

j = i + 1  # Correct: Start next partition after current one ends

The next partition should start at the position immediately after the current partition ends, not at the ending position itself.