Partition Labels medium

Problem Statement

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

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.

Example 2:

Input: s = "eccbbbbdec" Output: [10]

Steps

1. Last Occurrence Map: Create a map (dictionary in Python) to store the last occurrence index of each character in the string. Iterate through the string, updating the map for each character.

2. Partitioning: Initialize last_index to 0, max_index to 0, and the result list partitions to an empty list. Iterate through the string:

   • For each character's index i, find its last occurrence index from the map.
   • Update max_index to be the maximum of max_index and the last occurrence index.
   • If i is equal to max_index, it means we've reached the end of a partition. Append the partition size (max_index - last_index + 1) to partitions. Update last_index to max_index + 1.

3. Return: Return the partitions list.

Explanation

The algorithm works by greedily extending partitions. It keeps track of the maximum last occurrence index encountered so far (max_index). A partition ends when the current index i reaches this max_index. This ensures that all characters within that partition have their last occurrences within that partition. Therefore, no character is split across multiple partitions.

Code

def partitionLabels(s: str) -> list[int]:
    """
    Partitions a string into sub-strings such that each letter appears in at most one part.

    Args:
        s: The input string.

    Returns:
        A list of integers representing the sizes of the partitions.
    """

    last_occurrence = {}  # Map to store the last occurrence index of each character
    for i, char in enumerate(s):
        last_occurrence[char] = i

    last_index = 0
    max_index = 0
    partitions = []
    for i, char in enumerate(s):
        max_index = max(max_index, last_occurrence[char])
        if i == max_index:
            partitions.append(max_index - last_index + 1)
            last_index = max_index + 1

    return partitions

Complexity

• Time Complexity: O(N), where N is the length of the string. We iterate through the string twice (once to build the last_occurrence map, and once to partition).

• Space Complexity: O(1). The last_occurrence map will have at most 26 entries (for lowercase English letters), which is a constant space. The partitions list's space usage is also proportional to the number of partitions, which is at most N. Therefore, the space complexity is considered O(1) because it does not grow significantly with the input size N. This ignores the implicit stack space usage due to function calls which is usually relatively small and also considered constant.