Codeforces 141A Amusing Joke Solution & Explanation

Difficulty : 800

Problem Description

So, the New Year holidays are over. Santa Claus and his colleagues can take a rest and have guests at last. When two “New Year and Christmas Men” meet, thear assistants cut out of cardboard the letters from the guest’s name and the host’s name in honor of this event. Then the hung the letters above the main entrance. One night, when everyone went to bed, someone took all the letters of our characters’ names. Then he 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 of the host and his guests 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 the “New Year and Christmas Men” and their friends to cope with this problem. You are given both inscriptions that hung over the front door the previous night, and a pile of letters that were found at the front door next morning.

Input

The input file consists of three lines: the first line contains the guest’s name, the second line contains the name of the residence host and the third line contains letters in a pile that were found at the door in the morning. All lines are not empty and contain only uppercase Latin letters. The length of each line does not exceed 100.

Output

Print “YES” without the quotes, if the letters in the pile could be permuted to make the names of the “New Year and Christmas Men”. Otherwise, print “NO” without the quotes.

Examples

Note

In the first sample the letters written in the last line can be used to write the names and there won’t be any extra letters left.

In the second sample letter “P” is missing from the pile and there’s an extra letter “L”.

In the third sample there’s an extra letter “L”.

Solution

In our initial solution, we utilize a dictionary to store each character along with its frequency of occurrence.

C# Solution

Solution1

Dictionary<char,int> dict =   new Dictionary<char,int>();


string str1 = Console.ReadLine();
string str2 = Console.ReadLine();

foreach(var tmp in str1)
{
    if (!dict.ContainsKey(tmp))
    {
        dict.Add(tmp, 1);
    }
    else
    {
        dict[tmp] = dict[tmp]+1;
    }
}

foreach(var tmp in str2)
{
    if (!dict.ContainsKey(tmp))
    {
        dict.Add(tmp, 1);
    }
    else
    {
        dict[tmp] = dict[tmp]+1;
    }
}

string strChk = Console.ReadLine();
bool notfound = false;

foreach(var tmp in strChk)
{
    if (!dict.ContainsKey(tmp))
    {
        notfound = true;
        break;
    }
    else
    {
        var val = dict[tmp]-1;
        dict[tmp] = val;
        if(val==0){
            dict.Remove(tmp);
        }
    }
}

Console.WriteLine((dict.Count == 0 && !notfound) ? "YES" : "NO");

And if the appear times is equals to 0, we remove it from the dictionary, so that we can ensure each letter from the pile at the door matches the letters from the names hung over the entrance.

If any letter is not found in the dictionary (indicating it’s an extra letter), the variable ‘notfound’ is set to true. Finally, we verify whether there are any remaining letters in the dictionary.

If the dictionary is empty (indicating all necessary letters are accounted for) and ‘notfound’ is false (indicating no extra letters are found), we conclude that it is possible to restore the names

Conclusion

🧡If my solution helps, that is my honor!

🧡You can support me by sharing my posts, thanks you~~

✅If you got any problem about the explanation or you need other programming language solution, please feel free to let me know !!

The problem link : Problem – 141A – Codeforces

Similar Questions

• LeetCode #389 Find the Difference Solution & Explanation
• LeetCode #383 Ransom Note Solution & Explanation

Random Codeforces Posts