EDITORIAL INSCTS3 - Wonderland Jewellery
Problem Setter: @ani94
Editorialist : @kcahdog
Given a string A, find the lexicographically smallest string such that all letters with odd number of occurrences together come first in the string and letters with even numbers of occurrences come later.
This was the easiest problem of the lot.The main concept was storing the number of occurrences of each character in the string. This can be easily done using an array of size 26 as a hash table. The letter ‘a’ corresponds to array, b corresponds to array,……….
This hashing can be done using the ascii value of each character. The ascii value of each letter. The ascii value of a is 97 so ‘a’-97 will give 0.Similarly ‘z’ – 97 will give 25.
int hash; //initialize to zero for each test case Scanf( “%s” , input_string); //scan input, input_string is character array For( i=0; input_string[i]!= ‘\0’ ; i++) //traverse entire string Hash[ input_string[i] - 97 ] ++ //count occurences of each character
This step is O(N) . In the next step , we start from the first element of the hash table and print all the characters occurring odd number of times.We can then make another traversal of the hash table and print all the characters that occur even number of times. This gives the required string.
for(i=0;i<26; i++ ) //Odd number of occurrences if(arr[i]%2==1) for(j=0; j< arr[i]; j++ ) printf("%c",i+97); //Even number of occurrences for(i=0;i<26; i++ ) if(arr[i]%2==0) for(j=0; j< arr[i]; j++ ) printf("%c",i+97); printf("\n");
For people struggling with the concept of hashing characters to count the number of occurrences , I would suggest the Codechef problem Lapindromes which is based on a similar lines.