EDITORIAL INSCTS3 - Wonderland Jewellery
Problem Setter: @ani94
Editorialist : @kcahdog
Problem Statement:
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.
Solution:
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[0], b corresponds to array[1],ā¦ā¦ā¦.
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.
Sample Code:
int hash[26]; //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.
Sample Code:
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.