# Leetcode - Partition Labels

violet posted @ Jun 17, 2020 08:00:44 AM in 算法 with tags Algorithm Golang hash , 439 阅读

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
}```
Escorts in Chattarpu 说:
Jan 20, 2022 06:13:38 PM

Wonderful article. Fascinating to read. I love to read such an excellent article. Thanks! It has made my task more and extra easy. Keep rocking.

Question Paper 2024 说:
Feb 15, 2023 12:49:35 PM

Students taking the Board Exams should review the Board Question Paper 2024 in PDF format at the conclusion of this post. According to recent reports, a big number of applicants will take the Examinations in 2024. Question Paper 2024 All students are anxiously awaiting the Board Previous Paper 2024, Model Paper/Previous Paper 2024, Board Exam Question Paper 2024.

(输入验证码)
or Ctrl+Enter