Leetcode 1647 Minimum Deletions to Make Character Frequencies Unique
A string s
is called good if there are no two different characters in s
that have the same frequency.
Given a string s
, return the minimum number of characters you need to delete to make s
good.
The frequency of a character in a string is the number of times it appears in the string. For example, in the string "aab"
, the frequency of 'a'
is 2
, while the frequency of 'b'
is 1
.
Example 1:
Input: s = "aab"
Output: 0
Explanation: s is already good.
Example 2:
Input: s = "aaabbbcc"
Output: 2
Explanation: You can delete two 'b's resulting in the good string "aaabcc".
Another way it to delete one 'b' and one 'c' resulting in the good string "aaabbc".
Example 3:
Input: s = "ceabaacb"
Output: 2
Explanation: You can delete both 'c's resulting in the good string "eabaab".
Note that we only care about characters that are still in the string at the end (i.e. frequency of 0 is ignored).
Constraints:
1 <= s.length <= 105
s
contains only lowercase English letters.
//Java
import java.util.*;
class MinDeletions {
public static void main(String[] args) {
Solution sl = new Solution();
}
}
class Solution {
public int minDeletions(String s) {
int[] freq = new int[26];
for (char c : s.toCharArray()) {
freq[c - 'a']++;
}
Arrays.sort(freq);
int exp = freq[25];
int res = 0;
for (int i = 25; i >= 0; i--) {
if (freq[i] == 0)
break;
if (freq[i] > exp) {
res += freq[i] - exp;
} else {
exp = freq[i];
}
if (exp > 0) {
exp--; // Lowest exp is zero, cannot be negative
}
}
return res;
}
}//Javascript
var minDeletions = function(s) {
let freq = [...new Array(26)].map(()=>0);
let arr = s.split('');
for(let i = 0; i < arr.length; i++)
{
freq[arr[i].charCodeAt() - 'a'.charCodeAt()]++;
}
// console.log(freq);
freq.sort((a,b)=>a-b);
// freq.sort();
let exp = freq[25];
let res = 0;
for(let i = 25; i >-1; i--)
{
if( freq[i] == 0 )
break;
if(freq[i] > exp)
{
res += freq[i] - exp;
}else
{
exp = freq[i];
}
if(exp > 0)
exp--;
}
return res;
};
console.log(minDeletions("aaabbbcc"));//C#
public class Solution {
public int MinDeletions(string s) {
int[] freq = new int[26];
// char[] arr;
// arr = s.ToCharArray(0, s.Length);
foreach (char c in s.ToCharArray(0, s.Length)) {
freq[c - 'a']++;
}
Array.Sort(freq);
int exp = freq[25];
int res = 0;
for (int i = 25; i >= 0; i--) {
if (freq[i] == 0) break;
if (freq[i] > exp) {
res += freq[i] - exp;
} else {
exp = freq[i];
}
if (exp > 0) exp--; // Lowest exp is zero, cannot be negative
}
return res;
}
}