Question

Microsoft | OA Coding Questions and Solutions | Set - 73 | 2022

Answer 1

Minimum deletions required to make frequency of each letter unique
Input: "aabbffddeaee"
Output: 6
Input: "example"
Output: 4

Answer 2

Worked on those examples

 

def makeunique(str):

 

d = dict()
for x in str:
    if x in d:
        d[x]+=1
    else:
        d[x] = 1
c = sorted(d.items(),key = lambda x:-x[1])
cur = c[0][1] -1
out = 0

for freq in c[1:]:
    if cur == 0:
        out+=freq[1]
    elif freq[1] == cur:
        cur -=1
    elif freq[1] > cur:
        out+= freq[1] - cur
        cur -= 1
    else:
        cur = freq[1] - 1
return out

Answer 3

C++ Code:

 

    int minDeletions(string s) {
        vector<int> mp(26, 0);
        for(char c:s){
            mp[c-'a']++;
        }
        sort(mp.begin(), mp.end());
        int cnt=0;
        unordered_set<int> st;
        for(int i=mp.size()-1; i>=0;){
            if(mp[i]>0 && st.find(mp[i])!=st.end()){
                mp[i]--;
                cnt++;
            }else{
                st.insert(mp[i]);
                i--;
            }
        }
        return cnt;
    }