题目 #

You are given a string s consisting of the characters ‘a’, ‘b’, and ‘c’ and a non-negative integer k. Each minute, you may take either the leftmost character of s, or the rightmost character of s.

Return the minimum number of minutes needed for you to take at least k of each character, or return -1 if it is not possible to take k of each character.

Example 1:

Input: s = "aabaaaacaabc", k = 2
Output: 8
Explanation:
Take three characters from the left of s. You now have two 'a' characters, and one 'b' character.
Take five characters from the right of s. You now have four 'a' characters, two 'b' characters, and two 'c' characters.
A total of 3 + 5 = 8 minutes is needed.
It can be proven that 8 is the minimum number of minutes needed.

Example 2:

Input: s = "a", k = 1
Output: -1
Explanation: It is not possible to take one 'b' or 'c' so return -1.

  Constraints:

• $1 <= s.length <= 10^5$
• s consists of only the letters ‘a’, ‘b’, and ‘c’.
• $0 <= k <= s.length$

思路1 双指针 #

分析 #

• 先假设左侧没有，全部取右侧，能否满足要求，不满足就返回-1
• 满足要求开始缩减，右侧对应的位置的字母统计大于k就右移，右移到不能大于为止，判断和result是不是最小
• 然后将左侧指向的字符加入，下一个循环判断
• 当左侧大于当前最小结果就不用继续了，因为一定左侧加右侧大于当前结果

代码 #

 1func min(a, b int) int {
 2	if a < b {
 3		return a
 4	}
 5	return b
 6}
 7
 8func takeCharacters(s string, k int) int {
 9	if k == 0 {
10		return 0
11	}
12	chCount := make([]int, 3)
13	// 第一个for循环，查看左侧为0，右侧需要有多长
14	for r := len(s) - 1; r >= 0; r-- {
15		chCount[int(s[r]-'a')]++
16	}
17	for _, v := range chCount {
18		if v < k {
19			return -1
20		}
21	}
22
23	result := len(s)
24	r := 0
25	// l所在位置还没有被选入，下一个循环被选入，不用考虑最后一个，因为最后一个和r到第一个一样
26	for l := 0; l < result; l++ {
27		// 右侧对应的字符大于k，说明右侧可以移动
28		for r < len(s) && chCount[int(s[r]-'a')] > k {
29			chCount[int(s[r]-'a')]--
30			r++
31		}
32		result = min(result, l+len(s)-r)
33		chCount[int(s[l]-'a')]++
34	}
35
36	return result
37}