Partition Labels

Problem Statement

You are given a string s consisting of lowercase English letters.

We want to split the string into as many substrings as possible, while ensuring that each letter appears in at most one substring.

Return a list of integers representing the size of these substrings in the order they appear in the string.

Example 1:

# Input: s = "xyxxyzbzbbisl"
# Output: [5, 5, 1, 1, 1]
s = "xyxxyzbzbbisl"
print(partition_labels(s))

Explanation: The string can be split into ["xyxxy", "zbzbb", "i", "s", "l"].

Example 2:

# Input: s = "abcabc"
# Output: [6]
s = "abcabc"
print(partition_labels(s))

Constraints:

  • 1 <= s.length <= 100

You should aim for a solution with O(n) time and O(1) space, where n is the length of the string s.

Hint 1

Consider using a greedy approach to find the largest possible substring at each step.

Hint 2

Precompute the last occurrence of each character to determine the boundaries of the substrings.

Solution

Two Pointers (Greedy)

def partition_labels(s: str) -> list[int]:
    """
    Partitions a string into substrings such that each letter appears in at most one substring.
    """
    last_index = {}
    for i, char in enumerate(s):
        last_index[char] = i


    result = []
    size = end = 0
    for i, char in enumerate(s):
        size += 1
        end = max(end, last_index[char])


        if i == end:
            result.append(size)
            size = 0
    return result

Time complexity: O(n) Space complexity: O(1)

Where n is the length of the string s and since the length of the English alphabet is fixed, the space complexity is O(1).