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.

題目翻譯

必須說這題的敘述真的是有夠不明確的，看一下別人的討論才終於比較懂說要幹嘛。題目給定一個字串s，想要將其盡可能的拆分。但是有一個條件，就是同一個字母需要在同一個部分。表示說，今天有個字串s是"acbacdefe"，就只能拆成"acbac"和"defe"。因為一開始的a，所以要找到下一個a，但是第二個字母e之後又比最後一個a更後面。

解法解析

用一個 hash map 紀錄每個字母的最後出現的 index，然後去迭代 s 的所有值。使用anchor紀錄最開頭的值。 當 i相等於j(該字母最後出現的index值)，代表找到了拆分的地方，就將其長度(i-anchor)記錄到ans。

解法範例

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) {
                ans.add(j - anchor + 1)
                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
    }
}