Leetcode - Partition Labels

https://leetcode.com/problems/partition-labels/

A string S of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and 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.

func partitionLabels(S string) []int {
    hash := map[byte]int{}
    for i := 0; i < len(S); i++ {
        hash[S[i]] = i
    }
    last, start := 0, 0
    result := []int{}
    for i := 0; i < len(S); i++ {
        last = max(last, hash[S[i]])
        if last == i {
            result = append(result, last - start + 1)
            start = last + 1
        }
    }
    return result
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

• 相关文章
• 全局相关文章