Partition Labels

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. For example, the string "ababcc" can be partitioned into ["abab", "cc"], but partitions such as ["aba", "bcc"] or ["ab", "ab", "cc"] are invalid.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

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]

Constraints:

• 1 <= s.length <= 500
• s consists of lowercase English letters.

class Solution:
    def partitionLabels(self, s: str) -> list[int]:
        last_occurrence = {}
        for i, char in enumerate(s):
            last_occurrence[char] = i

        result = []
        start = 0
        end = 0

        for i, char in enumerate(s):
            end = max(end, last_occurrence[char])

            if i == end:
                result.append(end - start + 1)
                start = i + 1

        return result

Explanation:

1. Build the Last Occurrence Map:

• We first create a dictionary last_occurrence to store the last index where each character appears in the string s. This is done in the first loop.

1. Iterate and Determine Partitions:

• We initialize start and end to 0. The start variable marks the beginning of the current partition, and the end variable marks the farthest reach of the current partition.
• We iterate through the string s again. For each character, we update end to be the maximum of its current value and the last occurrence of the current character.
• If the current index i is equal to end, it means we've reached the end of the current partition. We append the length of the partition (end - start + 1) to the result list, and then update start to i + 1 to begin the next partition.

Example:

For the input string s = "ababcbacadefegdehijhklij":

1. The last_occurrence map will be:

   • {'a': 8, 'b': 5, 'c': 7, 'd': 14, 'e': 15, 'f': 11, 'g': 13, 'h': 16, 'i': 18, 'j': 19, 'k': 17, 'l': 20}

2. The algorithm proceeds as follows:

   • i = 0, char = 'a', end = 8
   • i = 1, char = 'b', end = 8
   • ...
   • i = 8, char = 'a', end = 8. Since i == end, we append 8 - 0 + 1 = 9 to the result and set start = 9.
   • i = 9, char = 'd', end = 14
   • ...
   • i = 15, char = 'e', end = 15. Since i == end, we append 15 - 9 + 1 = 7 to the result and set start = 16.
   • i = 16, char = 'h', end = 20
   • ...
   • i = 20, char = 'l', end = 20. Since i == end, we append 20 - 16 + 1 = 5 to the result and set start = 21.

3. The final result is [9, 7, 8].

Time and Space Complexity

Time Complexity: O(n), where n is the length of the string s. We iterate through the string twice.

Space Complexity: O(1). The last_occurrence dictionary stores at most 26 characters (lowercase English letters), so it takes constant space. The result list's size depends on the number of partitions, which in the worst case could be n, but on average will be much smaller. However, since the character set is fixed, the space used can be considered O(1).