LeetCode-in-All
763. Partition Labels
Medium
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]
Constraints:
1 <= s.length <= 500sconsists of lowercase English letters.
Solution
class Solution {
func partitionLabels(_ s: String) -> [Int] {
var last: [Character: Int] = [:]
for (i, char) in s.enumerated() {
last[char] = i
}
var result: [Int] = []
var start = 0
var end = 0
for (i, char) in s.enumerated() {
end = max(end, last[char, default: 0])
if i == end {
result.append(end - start + 1)
start = i + 1
end = i + 1
}
}
return result
}
}