Leetcode Minimum Deletions to Make Character Frequencies Unique | 1647 Easy

Posted on by

LeetCode 1647. Minimum Deletions to Make Character Frequencies Unique.

 

Question Link :  Minimum Deletions to Make Character Frequencies Unique

Question

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.

Solution:

Data Structures Used :

  • Vector
  • Unordered Set

Important : We use insert() function to insert element into the set container. It returns a pair object representing the result of the insertion. It returns two values:

  1. An iterator pointing to the position where the new element was inserted or the position of an equivalent element if the element being inserted already exists in the set.
  2. A boolean value that indicates whether the insertion was successful or not. It is true if the element was inserted and false if the element was not inserted because it already exists in the set.

Intuition: Count the frequency of the character in the string .Then simply try to insert the frequency in the set container and check what the insert function returns , it will return true if it is successfully inserted otherwise false.

Time Complexity: O(n)

Space Complexity : O(1)

Code for the Minimum Deletions to Make Character Frequencies Unique.

C++

class Solution {
 public:
  int minDeletions(string s) {
    int ans = 0;
    vector<int> Freq(26);
    unordered_set<int> usedFreq;

    for (char c : s)
    {  
// it will find corresponding index , 
//of the required character , a= 0, b= 1, c=2 
        Freq[c-'a'] ++ ; 
    }
      

    for (int freq : count)
     { 
         // keep decresing the value of frequency 
         //till you find a suitable place .
         while (freq > 0 && !usedFreq.insert(freq).second) { 
            freq --;  
            ans ++;
      }
     }

    return ans;
  }
};

 

Thank You ! Happy Coding .

 

CSES Longest Flight Route Solution 1680 | Topological Sort