763. 划分字母区间

题目描述

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

输入：s = “ababcbacadefegdehijhklij”
输出：[9,7,8]
解释：划分结果为 “ababcbaca”、“defegde”、“hijhklij” 。每个字母最多出现在一个片段中。像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的，因为划分的片段数较少。

示例 2：

输入：s = “eccbbbbdec”
输出：[10]

提示：

1 <= s.length <= 500
s 仅由小写英文字母组成

解法一：一次遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


func partitionLabels(s string) []int {
    n := len(s)
    record := make(map[byte]int)
    for i := n - 1; i >= 0; i-- {
        _, has := record[s[i]]
        if !has {
            record[s[i]] = i + 1
        }
    }
    var ans []int
    pos := 0
    for pos < n {
        nextPos := record[s[pos]]
        for i := pos; i < nextPos; i++ {
            if record[s[i]] > nextPos {
                nextPos = record[s[i]]
            }
        }
        ans = append(ans, nextPos-pos)
        pos = nextPos
    }
    return ans
}

官方题解如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


func partitionLabels(s string) (partition []int) {
    lastPos := [26]int{}
    for i, c := range s {
        lastPos[c-'a'] = i
    }
    start, end := 0, 0
    for i, c := range s {
        if lastPos[c-'a'] > end {
            end = lastPos[c-'a']
        }
        if i == end {
            partition = append(partition, end-start+1)
            start = end + 1
        }
    }
    return
}