Problem Link:
CONTEST
PRACTICE
Author- Sameer Taneja
Tester- Vipin Khushu
Editorialist- Kushank Arora
Difficulty:
Simple
Prerequisites:
Hashing
Problem:
The aim is to find 3 characters which has the maximum frequency and their corresponding frequencies.
Explanation:
The problem is to find 3 characters which has the maximum frequency. For this purpose, we need to have the frequency of all the characters. Before finding the frequency of every character, let us take an example to understand how frequency for each character is calculated? This is done using Hashing.
For an example, if there is a row in which 1000 people are standing each holding a card which is either red, green, blue or black. And the person has to note the number of people having the red card or green card or blue card or black card, the person makes 4 trays and ask each person to place their card in corresponding plates. Then he can easily find the number of cards for each color.
Similarly in our case, we will make 26 trays and each character in the string which deposit their identity in corresponding trays. This is done in this way:
tray[26] = 0 //Each element in the array is assigned zero
for i in len(str):
if(str[i] = ’a’ or str[i] = ’A’):
tray[0] = tray[0] + 1
else if(str[i] = ’b’ or str[i] = ’B’):
tray1 = tray1 + 1
so on c,d,e…y
else if(str[i] = ’z’ or str[i] = ’Z’):
tray[25] = tray[25] + 1
The above code is not the efficient code as it requires so many ifs and elses. Thus to make it efficient, we first convert the character to upper case(or lower case) and then decrement its ASSCII value by the ASCII value of ‘A’ (as the letters are consecutive in ASSCII). This gives us a number ranging from 0 to 25 where 0 is for A and 25 for Z. Thus or code becomes:
tray[26] = 0 //Each element in the array is assigned zero
for i in len(str):
if UPPER(str)>=’A’ and UPPER(str)<=’Z’ :
tray[UPPER(str[i]) – ‘A’] = tray[UPPER(str[i]) – ‘A’] + 1
Next step is to, find the maximum 3 of the array. For this firstly the maximum from the array is found and it is removed from the array. Then again the new maximum is found, and so on, till we have 3 maxima.
i = 0
while i < 3 :
j=0
max=0
while j < 26:
if(tray[j]>tray[max]):
max = j
j = j + 1
//max has the index of the character with maximum frequency, Use it here.
tray[max] = -1
i = i +1
Solution
http://ideone.com/wjwZem