763.划分字母区间 (Medium)

题目描述

样例

Input：S = "ababcbacadefegdehijhklij"
Output：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

题解

贪心算法，使用一个变量 end 记录每段字符的某位，每次更新字符的end 位置。

代码示例

Python 示例

class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        last = {}
        for idx, s in enumerate(S):
            last[s] = idx
        start, end = 0, 0
        label = []
        for idx, s in enumerate(S):
            end = max(end, last[s])
            if idx == end: # 走到end，划分字母
                label.append(end - start + 1)
                start = idx + 1 # 开新的区间           
        return label 

Go 示例

func max(a, b int) int {
    if a > b { return a}
    return b
}

func partitionLabels(S string) []int {
    n := len(S)
    last := make(map[rune]int, n)
    for idx, s := range S { // 记录字符的最后的位置
        last[s] = idx
    }
    start, end := 0, 0
    ans := make([]int, 0)
    for idx, s := range S {
        end = max(end, last[s]) //不停更新每个分段的end位置
        if idx == end {  // 走到end， 开始划分字母
            ans = append(ans, end - start + 1) // 计算长度，加入结果集中
            start = idx + 1
        }
    }
    return ans 
}