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
Recommended Time and Space Complexity
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 strings
and since the length of the English alphabet is fixed, the space complexity isO(1)
.