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 <= 105 0 <= k <= 105 word consists only of lowercase English letters. c++
Question
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 <= 105 0 <= k <= 105 word consists only of lowercase English letters. c++
Solution
Sure, here is a step-by-step solution in Python:
- First, we need to count the frequency of each character in the word. We can use a dictionary in Python to do this. The keys of the dictionary will be the characters in the word, and the values will be their frequencies.
from collections import Counter
freq = Counter(word)
- Next, we sort the frequencies in descending order. This is because we want to delete the least frequent characters first.
sorted_freq = sorted(freq.values(), reverse=True)
- Now, we iterate over the sorted frequencies. For each frequency, we check if it is larger than the next frequency plus k. If it is, we need to delete some characters to make the word k-special. The number of characters to delete is the difference between the current frequency and the next frequency plus k.
deletions = 0
for i in range(len(sorted_freq) - 1):
if sorted_freq[i] > sorted_freq[i+1] + k:
deletions += sorted_freq[i] - (sorted_freq[i+1] + k)
sorted_freq[i] = sorted_freq[i+1] + k
- Finally, we return the total number of deletions.
return deletions
Here is the complete function:
from collections import Counter
def min_deletions(word, k):
freq = Counter(word)
sorted_freq = sorted(freq.values(), reverse=True)
deletions = 0
for i in range(len(sorted_freq) - 1):
if sorted_freq[i] > sorted_freq[i+1] + k:
deletions += sorted_freq[i] - (sorted_freq[i+1] + k)
sorted_freq[i] = sorted_freq[i+1] + k
return deletions
This function works by ensuring that the frequency of each character in the word is at most k more than the frequency of the next least frequent character. This is done by deleting the necessary number of characters.
Similar Questions
You are given a string word of size n, and an integer k such that k divides n.In one operation, you can pick any two indices i and j, that are divisible by k, then replace the substring of length k starting at i with the substring of length k starting at j. That is, replace the substring word[i..i + k - 1] with the substring word[j..j + k - 1].Return the minimum number of operations required to make word k-periodic.We say that word is k-periodic if there is some string s of length k such that word can be obtained by concatenating s an arbitrary number of times. For example, if word == “ababab”, then word is 2-periodic for s = "ab". Example 1:Input: word = "leetcodeleet", k = 4Output: 1Explanation:We can obtain a 4-periodic string by picking i = 4 and j = 0. After this operation, word becomes equal to "leetleetleet".Example 2:Input: word = "leetcoleet", k = 2Output: 3Explanation:We can obtain a 2-periodic string by applying the operations in the table below.i j word0 2 etetcoleet4 0 etetetleet6 0 etetetetet Constraints:1 <= n == word.length <= 1051 <= k <= word.lengthk divides word.length.word consists only of lowercase English letters.
7.22 LAB: Word frequenciesWrite a program that reads a list of words. Then, the program outputs those words and their frequencies. The input begins with an integer indicating the number of words that follow. Assume that the list will always contain fewer than 20 words.Ex: If the input is:5 hey hi Mark hi markthe output is:hey - 1hi - 2Mark - 1hi - 2mark - 1Hint: Use two vectors, one vector for the strings and one vector for the frequencies.
You have given two strings 'A' and ‘B’ of length ‘N’ each which only consists of lowercase English letters. You have also given an integer ‘K’.Your task is to determine if it is possible to convert string ‘A’ into ‘B’ after performing two types of operations on it:1. Choose an index i (1 <= i <= N - 1) and swap A[i] and A[i+1].2. Choose an index i (1 <= i <= N - K + 1) and if A[i], A[i+1],. . . . , A[i+K-1] all are equal to some character x (x != ‘z’), then you can replace each one with the next character (x + 1) , i.e. ‘a’ is replaced by ‘b’, ‘b’ is replaced by ‘c’ and so on.Note:You are allowed to perform any operation any number of times(possibly zero) only on string 'A'.
Have the function LetterCount(str) take the str parameter being passed and return the first word with the greatest number of repeated letters. For example: "Today, is the greatest day ever!" should return greatest because it has 2 e's (and 2 t's) and it comes before ever which also has 2 e's. If there are no words with repeating letters return -1. Words will be separated by spaces.ExamplesInput: "Hello apple pie"Output: HelloInput: "No words"Output: -1
Given a string of lowercase alphabets, count all possible substrings (not necessarily distinct) that have exactly k distinct characters. Example 1:Input:S = "aba", K = 2Output:3Explanation:The substrings are: "ab", "ba" and "aba".
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.