Anagram Distance
InterviewTime limit1sMemory limit256 MB
Given many word pairs, count letters to delete from both so their letter frequency histograms match, using character counts.
- Level
Easy2 of 10
- Topics
- Hash map, String, Implementation
- Solved
- No attempts yet
Problem
If word A's letters can be rearranged to form word B, the two words are anagrams of each other. For example, occurs is an anagram of succor, but dear is not an anagram of dared. The most famous anagram in English is dog and god.
The anagram distance of two words is the minimum number of letters that must be deleted (from the two words in total) so that the two words become anagrams of each other. For example, given sleep and leap, deleting 2 letters from sleep and 1 letter from leap makes them anagrams, so the anagram distance of sleep and leap is 3. When there is no common letter at all, as in dog and cat, every letter must be deleted, so the anagram distance is 6.
Given two words, write a program that computes their anagram distance.
Input
The first line contains the number of test cases , a natural number at most 60,000. Each test case consists of two lines, each containing one word.
A word may have length 0 (an empty line) and consists only of lowercase letters. Only words that actually appear in an English dictionary are given; the longest word in the English dictionary is pneumonoultramicroscopicsilicovolcanoconiosis.
Output
For each test case, print one line in the form Case #x: d, where is the test case number starting from 1 and is the anagram distance of the two given words.