INSCRIPTION13 EDITORIAL-Wonderland Jewellery

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.

3 Likes

This was my exact solution as well, except I used the map data structure which can be seen as a high-level implementation of hash tables.

My code is below for reference:

#include <map>
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
#include <math.h>
#include <string>
using namespace std;

string mul(string s, int n)
{
	string ans = "";
	for(int i = 0; i < n; i++)
	{
		ans+=s;
	}
	return ans;
}

string rearrange(string s)
{
	string ans = "";
	map<string,int> m;
	for(int i = 0; i < s.size(); i++)
	{
		m[s.substr(i,1)]++;
	}
	set<string> ss;
	for(int i = 0; i < s.size(); i++)
	{
		ss.insert(s.substr(i,1));
	}
	vector<string> vec(ss.begin(), ss.end());
	sort(vec.begin(),vec.end());
	for(int i = 0; i < vec.size(); i++)
	{
		if(m[vec[i]]%2 != 0)
			ans += (mul(vec[i],m[vec[i]]));
	}
	for(int i = 0; i < vec.size(); i++)
	{
		if(m[vec[i]]%2 == 0)
			ans += (mul(vec[i],m[vec[i]]));
	}
	return ans;
	
}

int main()
{
	//odd before even
	int t;
	cin >> t;
	while(t--)
	{
		string s;
		cin >> s;
		cout << rearrange(s) << endl;
	}
	return 0;
}

This was a nice problem :smiley:

Bruno

@kuruma : Nice code. Infact I was the setter of this problem as a part of team INSCRIPTION .We were looking for some hash table implementation based question.Hope you liked the contest :slight_smile: