1647. Minimum Deletions to Make Character Frequencies Unique

 一刷 06/2022

Version #2 Sorting - better

Time O(N)

Space O(1)

Runtime: 12 ms, faster than 84.44% of Java online submissions for Minimum Deletions to Make Character Frequencies Unique.

Memory Usage: 53.8 MB, less than 78.50% of Java online submissions for Minimum Deletions to Make Character Frequencies Unique.

class Solution {

    public int minDeletions(String s) {

        int[] freq = new int[26];

        for (int i = 0; i < s.length(); i++) {

            freq[s.charAt(i) - 'a']++;

        }

        Arrays.sort(freq);

        int maxAllowed = s.length(); // Assuming this is the max freq that's not used

        int result = 0;

        for (int i = 25; i >= 0; i--) {

            if (freq[i] > maxAllowed) {

                result += freq[i] - maxAllowed; // current freq become the max allowed

            } else {

                // freq[i] <= maxAllowed

                maxAllowed = freq[i];

            }

            maxAllowed = maxAllowed == 0 ? 0 : maxAllowed - 1;

        }

        return result;

    }

}

Version #1 Intuitive Solution

Time O(N)

Space O(N)

Runtime: 24 ms, faster than 36.15% of Java online submissions for Minimum Deletions to Make Character Frequencies Unique.

Memory Usage: 54.5 MB, less than 46.42% of Java online submissions for Minimum Deletions to Make Character Frequencies Unique.

class Solution {

    public int minDeletions(String s) {

        int[] count = new int[26];

        int max = 0;

        for (int i = 0; i < s.length(); i++) {

            count[s.charAt(i) - 'a']++;

        }

        for (int i = 0; i < 26; i++) {

            max = Math.max(max, count[i]);

        }

        int[] freq = new int[max + 1];

        for (int i = 0; i < 26; i++) {

            freq[count[i]]++;

        }

        int change = 0;

        for (int i = freq.length - 1; i > 0; i--) {

            if (freq[i] > 1) {

                freq[i - 1] += freq[i] - 1;

                change += freq[i] - 1;

            }

        }

        return change;

    }

}