PROBLEM LINK:
Author: Subham Das
Tester: Soumik Sarkar
Editorialist: Subham Das
DIFFICULTY:
EASY
PREREQUISITES:
Basic knowledge of strings.
PROBLEM:
Determine the most frequent character at every instant, then print it and remove it from the string. Repeat until no character is left of the string. In case of a tie among most frequent characters, priority should be given to the lexicographically smaller one.
EXPLANATION
The size of the array N and the string a is provided to us within every test case. The first step should be to determine the number of times each character is present in the string. This could be done by having an array of size 26 (for each character in the lowercase alphabet) named as b.
for i 0 to 25
b[i] = 0
for i 0 to n-1
j = a[i]-'a';
b[j] = b[j]+1;
Then we have to find the maximum value present in array b and its position (the smallest position will be given priority as it is lexicographically smaller), decrement the value of b of that particular position by 1 and print the corresponding character. This could be done by the following algorithm.
for i 0 to n-1
k = 0
p = 0
for j 0 to 25
if(b[j] > k)
k = b[j]
p = j
b[p] -= 1;
print (char)(p+'a')
At the end we print a newline for each test case.
Complexity of the approach is \mathcal{O}(26 \times N).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.