Pular para o conteúdo principal

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:

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

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.

Alternative Solution (More Explicit)​

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

/**
 * 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;
}

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:

  1. 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

  2. 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