PROBLEM LINK:
Author: Anita Acha George
Tester: Alex Mathew
Editorialist: Alex Mathew
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
HASHING
PROBLEM:
Banta and his friends decide to play a game with names. They meet together and cut out alphabetical letters from a piece of waste cardboard which spell some names. After getting bored by playing for some time, they hang the letters of some two names above the main entrance of Banta’s House. That night, when everyone went to bed, someone took all the letters of the hung names and he/she may have shuffled the letters and put them in one pile in front of the door.
The next morning it was impossible to find the culprit who had made the disorder. But everybody wondered whether it is possible to restore the names from the letters lying at the door? That is, we need to verify that there are no extra letters, and that nobody will need to cut more letters.
Help Banta and his friends to cope with this problem. You are given both names that hung over the front door the previous night, and a pile of letters that were found at the front door next morning.
EXPLANATION:
This problem can be solved using an array A with size 128 which acts a counter for each character which is intialized to zero. The counter value of each character is increased by traversing both the original two strings. Decrease the counter value of all characters in the last string.
Now check if all the values in array A is 0. If yes then all letters are available and no more letters are needed. Otherwise they need to cut more letters.
FUNCTION TO CHECK THE SITUATION
int verifyLetters(char *firststr, char *secondstr, char *mixstr) {
int status = 0; // INITIALIZE THE FLAG
int dict[128] = {0}; //INITIALIZE ARRAY TO ZERO
int i;
//INCREMENTING THE COUNTER FOR FIRST TWO STRINGS
for (i = 0; i < strlen(firststr); i++)
dict[firststr[i]] += 1;
for (i = 0; i < strlen(secondstr); i++)
dict[secondstr[i]] += 1;
//DECREMENTING COUNTER FOR THIRD STRING
for (i = 0; i < strlen(mixstr); i++)
dict[mixstr[i]] -= 1;
//CHECKING THE COUNTER ARRAY
for(i = 0; i<128; i++) {
if(dict[i] != 0 ) {
status = 1; //SETTING STATUS TO 1
break;
}
}
return status;
}
OPTIMAL COMPLEXITY
O(X+Y+Z) where X – Length of first String
Y – Lenght of Second String
Z – Length of Third String
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.