763. Partition Labels

Leetcode link

题目简介

/**
 * @param {string} s
 * @return {number[]}
 */

题目给我们字符串 s，要求我们讲 s 分割成多个子字符串，要求不同的子字符串中不能有相同的字符元素

而且分割后的子字符串可以按顺序拼回字符串 s

最后返回每段子字符串的长度

解题思路

我们使用贪心的思路：

遍历字符串 s，对于每一个字符 char，我们都去寻找其在 s 中最后一次出现的下标

一旦遍历的指针 i 等于最后一次出现的下标，就表示我们找到了一段符合题意的子字符串

为了计算该字符串长度，我们需要一个变量 start 来记录上一个满足条件子字符串的后面第一个下标

这么一来我们就可以用 i-start+1 来求得长度了

Javascript

/**
 * @param {string} s
 * @return {number[]}
 */
var partitionLabels = function (s) {
    const len = s.length
    let left = 0
    let right = 0
    let lastIndices = new Map()
    const res = []

    for (let i = 0; i < len; i++) {
        lastIndices.set(s[i], i)
    }

    for (let i = 0; i < len; i++) {
        right = Math.max(right, lastIndices.get(s[i]))
        if (right === i) {
            res.push(right - left + 1)
            left = right + 1
        }
    }

    return res
};