Partition Labels

The goal is to partition the string into as many parts as possible so that each letter appears in at most one part. We can achieve this by following these steps:

  1. Find the Last Occurrence of Each Character: Create a dictionary that maps each character in the string to its last index of occurrence.

  2. Iterate Through the String and Partition: Initialize a variable start to mark the beginning of the current partition, and a variable end to mark the end of the current partition. Iterate through the string, and for each character, update end to be the maximum of its current value and the last index of occurrence of the current character. When the iteration index reaches end, add the length of the current partition to the result, and update start to begin the next partition.

  3. Return the Result: The result is the list of lengths of the partitions.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last_occurrence = {char: idx for idx, char in enumerate(s)}
        start, end = 0, 0
        result = []

        for i, char in enumerate(s):
            end = max(end, last_occurrence[char])
            if i == end:
                result.append(i - start + 1)
                start = i + 1

        return result

Example

  • s = "ababcbacadefegdehijhklij"
  • last_occurrence = {'a': 8, 'b': 5, 'c': 7, 'd': 14, 'e': 15, 'f': 11, 'g': 13, 'h': 19, 'i': 22, 'j': 23, 'k': 20, 'l': 21}
  • result = [9,7,8]

Insights

  • Efficiency: The time complexity of this algorithm is (O(n)), where (n) is the length of the string s. This is because we iterate through the string twice: once to find the last occurrence of each character, and once to partition the string.
  • Constraints: The constraints are satisfied as the approach works for strings of length up to 500 consisting of lowercase English letters.
  • Partitioning Logic: By keeping track of the last occurrence of each character in the current partition, we ensure that each letter appears in at most one part, satisfying the problem’s requirements.

Define the Terms Partition Label

Partition the given string into as many parts as possible so that each letter appears in at most one part. The letter must appear only in one part. It cannot appear in more than one partition.

Define the Interface Input: string Ouput: array of integers (representing the size of these partitions)

Analyze the Input and Output

Identify the Invariants

Identify the constraints

  • S will have length in range [1, 500].
  • S will consist of lowercase English letters (‘a’ to ‘z’) only.

Search the Problem Space as many parts as possible =>

Classify the Problem

Optimization problem Constraint is given

Analyze the Examples We start from the first character. We check when this first character end. All the letters between this start and end must also be within this partition. They cannot be in another partition also. a, b and c must be within this partition only.

Solve the Problem by Hand

Scan the string from the start and partition the label Find the size of the partition Add it to the output Repeat until we have scanned the entire string

Describe the Pattern

Distill the Observations to Create Insights

Brute Force Approach If we have a string that has the first letter which is not repeated anywhere else, then it is in its own partition.

You want to keep all the unique letters in a set. How do we end the partition?

Using a Window Keep track of the indices where we have last seen a letter.

012345678910 “ababcbacadefegdehijhklij”

a -> 8 b -> 5 c -> 7 d -> 14 e -> 16 f -> 12 g -> 14 h -> 19 i -> 22 j -> 23 k -> 20 l -> 21

a -> [0, 8] - First interval b -> [1, 5] - Second interval (within the first one) c -> [4, 7] - Third interval (within the first one) d -> [10, 14] e -> [11, 16] f -> [12] g -> [14]

start -> 10 and end -> 16

h -> [17, 19]

This addresses how to find the end of the partition. We see that d is starting at 10, whereas the previous 3 letters end at 8

Time: O(N) Space: O(N)

“ababcbacadefegdehijhklij” ^ ^

abcedefgh ^ ^

Time: O(N^2) Space: O(1)

Time: O(N) Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# @param {String} s
# @return {Integer[]}
def partition_labels(s)
  last = Array.new(26, 0)
  for i in (0...s.size)
     last[s[i].ord - 'a'.ord] = i 
  end

  j = 0
  anchor = 0
  output = []
    
  for i in (0...s.size)
     j = [j, last[s[i].ord - 'a'.ord]].max

     if i == j
        output << (i - anchor + 1) 
        anchor = i + 1 
     end
  end

  return output
end