763.M 划分字母区间

Problem: 763. 划分字母区间

思路

贪心算法。

由于一个字母只能出现在一个片段，因此对于某个字母而言，第一次出现的位置和最后一次出现的位置一定在同一个片段。所以可以用贪心算法来实现，维护一个区间[start, end]，从start开始不断遍历字符，把end更新为当前字符出现的最后一个位置（如果该位置大于当前end的话）。 如果已到达end的位置，说明找到了一个符合要求的片段。

Code

func partitionLabels(s string) []int {
	lastIndex := make(map[byte]int)
	for i, ch := range s {
		lastIndex[byte(ch)] = i
	}

	start, end := 0, 0
	var ans []int
	for i := 0; i < len(s); i++ {
		if lastIndex[s[i]] > end {
			end = lastIndex[s[i]]
		}

		if i == end {
			ans = append(ans, end-start+1)
			start = i + 1
		}
	}

	return ans
}