# Unique String Frequencies - Microsoft Top Interview Questions

### Problem Statement :

```Given a lowercase alphabet string s, return the minimum number of characters that we need to delete such that the frequency of each character occurs a unique number of times.

Constraints

n ≤ 100,000 where n is the length of s

Example 1

Input

s = "aabb"

Output

1

Explanation

Both "a" and "b" occur twice, so we can remove say "a" once to make the frequencies unique.

Example 2

Input

s = "abbccc"

Output

0

Explanation

The string already has unique frequencies for "a", "b" and "c": [1, 2, 3].```

### Solution :

```                        ```Solution in C++ :

int solve(string s) {
unordered_map<char, int> freq;
for (auto& c : s) freq[c]++;
vector<int> freqCounts;
for (auto& p : freq) freqCounts.push_back(p.second);
sort(freqCounts.rbegin(), freqCounts.rend());
int ret = 0;
int lastFreq = 1e9;
for (int freq : freqCounts) {
// freq must be at most lastFreq
if (freq > lastFreq) {
int rem = freq - lastFreq;
ret += rem;
freq -= rem;
}
lastFreq = max(0, freq - 1);
}
return ret;
}```
```

```                        ```Solution in Java :

import java.util.*;

class Solution {
public int solve(String s) {
// how many times does char "i" appear?
int[] occ = new int[26];
for (char c : s.toCharArray()) occ[c - 'a'] += 1;

// how many letters appear "i" times?
int[] freq = new int[s.length() + 1];
for (int i = 0; i < 26; i++) {
if (occ[i] > 0)
freq[occ[i]] += 1;
}

// greedy algorithim
int ans = 0;
for (int i = s.length(); i >= 1; i--) {
if (freq[i] > 1) {
ans += (freq[i] - 1);
freq[i - 1] += (freq[i] - 1);
}
}
return ans;
}
}```
```

```                        ```Solution in Python :

class Solution:
def solve(self, s):

freq = Counter(s)
deletions = 0
unique = set()
for f in freq.values():
if f in unique:
while f in unique and f > 0:
f -= 1
deletions += 1
return deletions```
```

## Down to Zero II

You are given Q queries. Each query consists of a single number N. You can perform any of the 2 operations N on in each move: 1: If we take 2 integers a and b where , N = a * b , then we can change N = max( a, b ) 2: Decrease the value of N by 1. Determine the minimum number of moves required to reduce the value of N to 0. Input Format The first line contains the integer Q.

## Truck Tour

Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no petr

## Queries with Fixed Length

Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression: In other words, if we let , then you need to calculate . Given and queries, return a list of answers to each query. Example The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is . The secon

## QHEAP1

This question is designed to help you get a better understanding of basic heap operations. You will be given queries of types: " 1 v " - Add an element to the heap. " 2 v " - Delete the element from the heap. "3" - Print the minimum of all the elements in the heap. NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct element