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).