成为 K 特殊字符串需要删除的最少字符数
难度:
标签:
题目描述
You are given a string word and an integer k.
We consider word to be k-special if |freq(word[i]) - freq(word[j])| <= k for all indices i and j in the string.
Here, freq(x) denotes the frequency of the character x in word, and |y| denotes the absolute value of y.
Return the minimum number of characters you need to delete to make word k-special.
Example 1:
Input: word = "aabcaba", k = 0
Output: 3
Explanation: We can make word 0-special by deleting 2 occurrences of "a" and 1 occurrence of "c". Therefore, word becomes equal to "baba" where freq('a') == freq('b') == 2.
Example 2:
Input: word = "dabdcbdcdcd", k = 2
Output: 2
Explanation: We can make word 2-special by deleting 1 occurrence of "a" and 1 occurrence of "d". Therefore, word becomes equal to "bdcbdcdcd" where freq('b') == 2, freq('c') == 3, and freq('d') == 4.
Example 3:
Input: word = "aaabaaa", k = 2
Output: 1
Explanation: We can make word 2-special by deleting 1 occurrence of "b". Therefore, word becomes equal to "aaaaaa" where each letter's frequency is now uniformly 6.
Constraints:
1 <= word.length <= 1050 <= k <= 105wordconsists only of lowercase English letters.
代码结果
运行时间: 67 ms, 内存: 16.3 MB
/*
* 思路：
* 1. 使用Java Stream API统计每个字符的频率。
* 2. 将这些频率进行排序。
* 3. 使用滑动窗口检查在给定k值的范围内，删除最少字符后能使得所有字符的频率差不超过k。
*/
import java.util.*;
import java.util.stream.Collectors;
public class KSpecialStringStream {
public int minDeletions(String word, int k) {
Map<Character, Long> frequencyMap = word.chars()
.mapToObj(c -> (char) c)
.collect(Collectors.groupingBy(c -> c, Collectors.counting()));
List<Long> frequencies = frequencyMap.values().stream().sorted().collect(Collectors.toList());
int minDeletions = Integer.MAX_VALUE;
for (int i = 0; i < frequencies.size(); i++) {
int deletions = 0;
for (int j = 0; j < frequencies.size(); j++) {
if (Math.abs(frequencies.get(i) - frequencies.get(j)) > k) {
deletions += Math.abs(frequencies.get(i) - frequencies.get(j)) - k;
}
}
minDeletions = Math.min(minDeletions, deletions);
}
return minDeletions;
}
public static void main(String[] args) {
KSpecialStringStream solver = new KSpecialStringStream();
System.out.println(solver.minDeletions("aabcaba", 0)); // 输出：3
System.out.println(solver.minDeletions("dabdcbdcdcd", 2)); // 输出：2
System.out.println(solver.minDeletions("aaabaaa", 2)); // 输出：1
}
}
解释
方法:
时间复杂度:
空间复杂度: