763. Partition Labels #

Problem #

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.

Main Idea #

This problem tests the sliding window problem.

Given a string, output the lengths of windows that satisfy the condition. The condition is that within this window, the letters appear in this window and do not appear in other windows.

Solution Ideas #

There are 2 approaches to this problem. The first approach is to first record the occurrence count of each letter, then determine for each letter in the sliding window whether its count has been used up and become 0. If the counts of all letters in this window are 0, then this window is a valid window. The time complexity is O(n).

Another approach is to record the index of the last occurrence of each character, so there is no need to record counts. In each sliding window, determine in order the position of the last occurrence of each letter. If, within an index, the last occurrence positions of all letters have been included, then this index is the size of the window that satisfies the condition. The time complexity is O(n^2).

Code #

package leetcode

// Solution one
func partitionLabels(S string) []int {
	var lastIndexOf [26]int
	for i, v := range S {
		lastIndexOf[v-'a'] = i
	}

	var arr []int
	for 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
}

// Solution two
func partitionLabels1(S string) []int {
	visit, counter, res, sum, lastLength := make([]int, 26), map[byte]int{}, []int{}, 0, 0
	for i := 0; i < len(S); i++ {
		counter[S[i]]++
	}

	for i := 0; i < len(S); i++ {
		counter[S[i]]--
		visit[S[i]-'a'] = 1
		sum = 0
		for 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
}