Partition Labels - Leetcode Solution

Problem:

A string S of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:

Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.

Note:

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

Solution:

One way to approach this problem is with a greedy algorithm that iterates over the string while keeping track of the last occurrence of each character. At each step, we look for the rightmost occurrence of any character within the current substring, and we partition the string at that position. Then we update our starting position to be the next position after the partition.

Here is the algorithm in more detail:

• Initialize a dictionary last_occurrence that maps each character to its last occurrence in the string.
• Initialize two pointers start and end to 0.
• For each letter c in the string:
  • Update end to be the maximum of its current value and last_occurrence[c].
  • If we have reached the rightmost occurrence of any letter in the substring from start to end:
    • Append the length of the current partition (end - start + 1) to the result list.
    • Update start to be the next position after the partition (end + 1).
• Return the result list.

Here is the Python code that implements this algorithm:

def partitionLabels(S): last_occurrence = {c: i for i, c in enumerate(S)} result = [] start = end = 0 for i, c in enumerate(S): end = max(end, last_occurrence[c]) if i == end: result.append(end - start + 1) start = i + 1 return result

This algorithm has a time complexity of O(n), where n is the length of the string, because we process each character in the string once. It also has a space complexity of O(1), because we only use a fixed-size dictionary and a few pointers to keep track of the state of the algorithm.

1