题目

A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and 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.

Note:

• S will have length in range [1, 500].
• S will consist of lowercase letters ('a' to 'z') only.

题目大意

这道题考察的是滑动窗口的问题。

给出一个字符串，要求输出满足条件窗口的长度，条件是在这个窗口内，字母中出现在这一个窗口内，不出现在其他窗口内。

解题思路

这一题有 2 种思路，第一种思路是先记录下每个字母的出现次数，然后对滑动窗口中的每个字母判断次数是否用尽为 0，如果这个窗口内的所有字母次数都为 0，这个窗口就是符合条件的窗口。时间复杂度为 O(n^2)

另外一种思路是记录下每个字符最后一次出现的下标，这样就不用记录次数。在每个滑动窗口中，依次判断每个字母最后一次出现的位置，如果在一个下标内，所有字母的最后一次出现的位置都包含进来了，那么这个下标就是这个满足条件的窗口大小。时间复杂度为 O(n^2) 度为 O(n^2)

参考代码

package leetcode// 解法一
func partitionLabels(S string) []int {var lastIndexOf [26]intfor i, v := range S {lastIndexOf[v-'a'] = i}var arr []intfor start, end := 0, 0; start < len(S); start = end + 1 {end = lastIndexOf[S[start]-'a']for i := start; i < end; i++ {if end < lastIndexOf[S[i]-'a'] {end = lastIndexOf[S[i]-'a']}}arr = append(arr, end-start+1)}return arr
}// 解法二
func partitionLabels1(S string) []int {visit, counter, res, sum, lastLength := make([]int, 26), map[byte]int{}, []int{}, 0, 0for i := 0; i < len(S); i++ {counter[S[i]]++}for i := 0; i < len(S); i++ {counter[S[i]]--visit[S[i]-'a'] = 1sum = 0for j := 0; j < 26; j++ {if visit[j] == 1 {sum += counter[byte('a'+j)]}}if sum == 0 {res = append(res, i+1-lastLength)lastLength += i + 1 - lastLength}}return res
}