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:

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
    }
}