Partition Labels

Given a string s containing only lowercase characters, return a list of integers representing the size of each substring you can create such that each character in s only appears in one substring.

Note: Each character must appear in exactly one partition, and we want to partition the string into as many parts as possible.

Example(s)

Example 1:

Input: s = "abacdddecn"
Output: [3, 6, 1]
Explanation:
- Partition 1: "aba" (size 3)
  Characters 'a' and 'b' only appear in this partition
- Partition 2: "cdddec" (size 6)
  Characters 'c' and 'd' only appear in this partition
- Partition 3: "n" (size 1)
  Character 'n' only appears in this partition

Example 2:

Input: s = "aba"
Output: [3]
Explanation:
- Partition 1: "aba" (size 3)
  Character 'a' appears at positions 0 and 2, so they must be in the same partition

Example 3:

Input: s = "ababcbacadefegdehijhklij"
Output: [9, 7, 8]
Explanation:
- Partition 1: "ababcbaca" (size 9)
- Partition 2: "defegde" (size 7)
- Partition 3: "hijhklij" (size 8)

Solution

The solution uses a greedy approach with two passes:

First pass: Find the last occurrence of each character
Second pass: Traverse the string and track the furthest position we need to reach
Partition detection: When we reach the furthest position, we've completed a partition
Record size: Add the size of the current partition to the result

JavaScript Solution
Python Solution

JavaScript Solution

/**
* Partition string into substrings with unique characters
* @param {string} s - Input string
* @return {number[]} - Sizes of each partition
*/
function partitionLabels(s) {
// Step 1: Find the last occurrence of each character
const lastOccurrence = new Map();
for (let i = 0; i < s.length; i++) {
  lastOccurrence.set(s[i], i);
}

const result = [];
let start = 0; // Start of current partition
let end = 0;   // End of current partition (furthest position we need to reach)

// Step 2: Traverse the string and create partitions
for (let i = 0; i < s.length; i++) {
  // Update end to the furthest last occurrence of any character seen so far
  end = Math.max(end, lastOccurrence.get(s[i]));
  
  // If we've reached the end of the current partition
  if (i === end) {
    // Calculate size of current partition
    result.push(end - start + 1);
    // Start a new partition
    start = i + 1;
  }
}

return result;
}

// Test cases
console.log('Example 1:', partitionLabels("abacdddecn")); 
// [3, 6, 1]

console.log('Example 2:', partitionLabels("aba")); 
// [3]

console.log('Example 3:', partitionLabels("ababcbacadefegdehijhklij")); 
// [9, 7, 8]

console.log('Test 4:', partitionLabels("eccbbbbdec")); 
// [10]

console.log('Test 5:', partitionLabels("abc")); 
// [1, 1, 1]

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

from typing import List

def partition_labels(s: str) -> List[int]:
  """
  Partition string into substrings with unique characters
  
  Args:
      s: Input string
      
  Returns:
      List[int]: Sizes of each partition
  """
  # Step 1: Find the last occurrence of each character
  last_occurrence = {}
  for i, char in enumerate(s):
      last_occurrence[char] = i
  
  result = []
  start = 0  # Start of current partition
  end = 0    # End of current partition (furthest position we need to reach)
  
  # Step 2: Traverse the string and create partitions
  for i, char in enumerate(s):
      # Update end to the furthest last occurrence of any character seen so far
      end = max(end, last_occurrence[char])
      
      # If we've reached the end of the current partition
      if i == end:
          # Calculate size of current partition
          result.append(end - start + 1)
          # Start a new partition
          start = i + 1
  
  return result

# Test cases
print('Example 1:', partition_labels("abacdddecn"))  
# [3, 6, 1]

print('Example 2:', partition_labels("aba"))  
# [3]

print('Example 3:', partition_labels("ababcbacadefegdehijhklij"))  
# [9, 7, 8]

print('Test 4:', partition_labels("eccbbbbdec"))  
# [10]

print('Test 5:', partition_labels("abc"))  
# [1, 1, 1]

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (More Explicit)

Here's a more explicit version that might be easier to understand:

JavaScript Alternative
Python Alternative

/**
 * Alternative: More explicit version
 */
function partitionLabelsExplicit(s) {
  // Find last occurrence of each character
  const lastIndex = {};
  for (let i = 0; i < s.length; i++) {
    lastIndex[s[i]] = i;
  }
  
  const partitions = [];
  let partitionStart = 0;
  let partitionEnd = 0;
  
  for (let i = 0; i < s.length; i++) {
    const char = s[i];
    const lastPos = lastIndex[char];
    
    // Extend the current partition to include this character's last occurrence
    partitionEnd = Math.max(partitionEnd, lastPos);
    
    // If we've processed all characters up to the partition end
    if (i === partitionEnd) {
      // Record the size of this partition
      partitions.push(partitionEnd - partitionStart + 1);
      // Start a new partition
      partitionStart = i + 1;
    }
  }
  
  return partitions;
}

def partition_labels_explicit(s: str) -> List[int]:
    """
    Alternative: More explicit version
    """
    # Find last occurrence of each character
    last_index = {}
    for i, char in enumerate(s):
        last_index[char] = i
    
    partitions = []
    partition_start = 0
    partition_end = 0
    
    for i, char in enumerate(s):
        last_pos = last_index[char]
        
        # Extend the current partition to include this character's last occurrence
        partition_end = max(partition_end, last_pos)
        
        # If we've processed all characters up to the partition end
        if i == partition_end:
            # Record the size of this partition
            partitions.append(partition_end - partition_start + 1)
            # Start a new partition
            partition_start = i + 1
    
    return partitions

Complexity

Time Complexity: O(n) - Where n is the length of the string. We make two passes through the string: one to find last occurrences, and one to create partitions.
Space Complexity: O(1) - We use a map to store last occurrences, but since there are at most 26 lowercase letters, the space is O(1). The result array is not counted in space complexity.

Approach

The solution uses a greedy two-pass algorithm:

First pass - Find last occurrences:
- Create a map storing the last index where each character appears
- This tells us how far we need to extend each partition
Second pass - Create partitions:
- Traverse the string from left to right
- For each character, update end to the maximum of:
  - Current end value
  - Last occurrence of current character
- When i === end, we've completed a partition:
  - Record the size: end - start + 1
  - Start a new partition at i + 1

Key Insights

Last occurrence matters: If a character appears at position i, we must include it in the partition until its last occurrence
Greedy approach: We extend the current partition as far as necessary
Partition boundary: When we reach the furthest position needed, we can safely end the partition
Two-pass algorithm: First pass to gather information, second pass to use it
O(n) time: Linear time complexity is optimal

Step-by-Step Example

Let's trace through Example 1: s = "abacdddecn"

Step 1: Find last occurrences
  'a': last at index 2
  'b': last at index 1
  'c': last at index 7
  'd': last at index 6
  'e': last at index 8
  'n': last at index 9

Step 2: Create partitions
  i=0: char='a', last=2, end=max(0,2)=2
  i=1: char='b', last=1, end=max(2,1)=2
  i=2: char='a', last=2, end=max(2,2)=2
    i === end → partition complete!
    size = 2 - 0 + 1 = 3
    result = [3]
    start = 3
  
  i=3: char='c', last=7, end=max(0,7)=7
  i=4: char='d', last=6, end=max(7,6)=7
  i=5: char='d', last=6, end=max(7,6)=7
  i=6: char='d', last=6, end=max(7,6)=7
  i=7: char='e', last=8, end=max(7,8)=8
  i=8: char='c', last=7, end=max(8,7)=8
    i === end → partition complete!
    size = 8 - 3 + 1 = 6
    result = [3, 6]
    start = 9
  
  i=9: char='n', last=9, end=max(0,9)=9
    i === end → partition complete!
    size = 9 - 9 + 1 = 1
    result = [3, 6, 1]

Final: [3, 6, 1]

Visual Representation

String:  a b a c d d d e c n
Index:   0 1 2 3 4 5 6 7 8 9

Last occurrence:
  a: 2, b: 1, c: 7, d: 6, e: 8, n: 9

Partition 1: [0-2] "aba" (size 3)
  - 'a' appears at 0, 2 → must include up to 2
  - 'b' appears at 1 → must include up to 1
  - Furthest: 2

Partition 2: [3-8] "cdddec" (size 6)
  - 'c' appears at 3, 8 → must include up to 8
  - 'd' appears at 4, 5, 6 → must include up to 6
  - 'e' appears at 7 → must include up to 8
  - Furthest: 8

Partition 3: [9-9] "n" (size 1)
  - 'n' appears at 9 → must include up to 9

Edge Cases

All unique characters: s = "abc" → [1, 1, 1] (each character is its own partition)
All same character: s = "aaa" → [3] (all must be in one partition)
Single character: s = "a" → [1]
No repeats: s = "abcdef" → [1, 1, 1, 1, 1, 1]
All repeats: s = "ababab" → [6] (all must be together)

Important Notes

Each character appears once: The constraint is that each character appears in exactly one partition
Maximize partitions: We want as many partitions as possible (greedy)
Last occurrence rule: If a character appears multiple times, all occurrences must be in the same partition
Lowercase only: Problem states only lowercase characters, so we have at most 26 unique characters

Merge Intervals: Similar concept of grouping related elements
Non-overlapping Intervals: Related interval problem
Partition Array: Different partitioning problem
Group Anagrams: Grouping related strings

Takeaways

Two-pass algorithm is efficient: gather information first, then use it
Greedy approach works: extend partition as far as needed
Last occurrence tracking is the key insight
O(n) time is optimal for this problem
Hash map is perfect for tracking last occurrences

Example(s)​

Solution​

JavaScript Solution

Output:

Python Solution

Output:

Alternative Solution (More Explicit)​

Complexity​

Approach​

Key Insights​

Step-by-Step Example​

Visual Representation​

Edge Cases​

Important Notes​

Related Problems​

Takeaways​

Example(s)

Solution

Alternative Solution (More Explicit)

Complexity

Approach

Key Insights

Step-by-Step Example

Visual Representation

Edge Cases

Important Notes

Related Problems

Takeaways