# 763. Partition Labels

## 題目敘述

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.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be `s`.

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 <= 500`
• `s` consists of lowercase English letters.

Hint 1:

Try to greedily choose the smallest partition that includes the first letter. If you have something like `"abaccbdeffed"`, then you might need to add b. You can use an map like `"last['b'] = 5"` to help you expand the width of your partition.

## 解法解析

### 解法範例

#### Go

``````func partitionLabels(s string) []int {
last := make(map[rune]int)
for i, c := range s {
last[c] = i
}

var anchor int = -1
var j int
var ans []int

for i, c := range s {
if last[c] > j {
j = last[c]
}

if i == j {
ans = append(ans, i-anchor)
anchor = i
}
}
return ans
}
``````

#### JavaScript

``````/**
* @param {string} s
* @return {number[]}
*/
var partitionLabels = function (s) {
const last = {};
for (let i = 0; i < s.length; i++) {
last[s[i]] = i;
}
let j = 0,
anchor = -1;
const ans = [];
for (let i = 0; i < s.length; i++) {
j = Math.max(j, last[s[i]]);
if (i === j) {
ans.push(i - anchor);
anchor = i;
}
}
return ans;
};
``````

#### Kotlin

``````class Solution {
fun partitionLabels(s: String): List<Int> {
val ans = mutableListOf<Int>()

val last = IntArray(26)
for ((i, c) in s.withIndex()) {
last[c - 'a'] = i
}

var anchor = 0
var j = last[s[0] - 'a']
for (i in s.indices) {
j = maxOf(j, last[s[i] - 'a'])

if (i == j) {
anchor = j + 1
}
}

return ans
}
}
``````

#### PHP

``````class Solution
{

/**
* @param String \$s
* @return Integer[]
*/
function partitionLabels(\$s)
{
\$len = strlen(\$s);
\$last = [];
\$ans = [];
for (\$i = 0; \$i < \$len; \$i++) {
\$last[\$s[\$i]] = \$i;
}
\$anchor = -1;
\$j = 0;
for (\$i = 0; \$i < \$len; \$i++) {
\$j = max(\$j, \$last[\$s[\$i]]);
if (\$i == \$j) {
array_push(\$ans, \$j - \$anchor);
\$anchor = \$j;
}
}
return \$ans;
}
}
``````

#### Python

``````class Solution:
def partitionLabels(self, s: str) -> List[int]:
last = {c: i for i, c in enumerate(s)}
j = 0
anchor = -1
ans = []
for i, c in enumerate(s):
j = max(j, last[c])
if i == j:
ans.append(i - anchor)
anchor = i

return ans
``````

#### Rust

``````use std::collections::HashMap;

impl Solution {
pub fn partition_labels(s: String) -> Vec<i32> {
let mut ans = Vec::<i32>::new();
let mut last = HashMap::<char,_>::new();
for (i, c) in s.chars().enumerate() {
last.insert(c, i);
}
let mut anchor = 0;
let mut j = 0;
for( i, c) in s.chars().enumerate() {
j = j.max(*last.get(&c).unwrap());
if i == j {
ans.push((j - anchor + 1) as i32);
anchor = j + 1;
}
}
ans
}
}
``````

#### Swift

``````class Solution {
func partitionLabels(_ s: String) -> [Int] {
var last = [Character:Int]()
for (i, c) in s.enumerated() {
last[c, default: 0] = i
}

var ans = [Int]()
var j = 0
var anchor = -1
for (i, c) in s.enumerated() {
j = max(j, last[c, default: 0])
if i == j {
ans.append(i - anchor)
anchor = i
}
}
return ans
}
}
``````