TopCoder problem "SimilarWords" used in TCHS08 Round 3 (Division I Level One)



Problem Statement

    The similarity of two words is the number of letters they share in common. Letter comparisons are case insensitive, and each occurrence of a letter counts only once. More precisely, if the same letter appears k times in the first word and m times in the second word, then this letter contributes minimum(k, m) to the similarity (see example 0 for clarification). You are given a String[] words, each element of which is a single word. Find a pair of words among them with the greatest similarity and return that similarity.
 

Definition

    
Class:SimilarWords
Method:mostSimilarPair
Parameters:String[]
Returns:int
Method signature:int mostSimilarPair(String[] words)
(be sure your method is public)
    
 

Constraints

-words will contain between 2 and 50 elements, inclusive.
-Each element of words will contain between 1 and 50 characters, inclusive.
-Each element of words will contain only letters ('a'-'z', 'A'-'Z').
 

Examples

0)
    
{ "aaB", "AbaAc" }
Returns: 3
The similarity is 3 because there are two occurrences of the letter 'a' and one occurrence of the letter 'b' in each word.
1)
    
{ "abcdefg", "ABCDEFG" }
Returns: 7
2)
    
{ "alnHFDfosKYFREanfETRiesf",
  "fjsHDdoAFifASsd",
  "GSDgsdGsdgJUsg",
  "KJmgnsNSFsngfn",
  "njtdhMHGBSmnytgnGVNR" }
Returns: 11
3)
    
{ "cdnepzoawAYtsHnYRLo", "DQYreVrBBrV",
  "KXvPqDZZSqjFbL", "JvrWjwnJEtvHav",
  "UzwHVAltvxp", "MPhEhzAEwSe", "wuCpYpDtJDakc",
  "fRHzYSonTYyBvSK", "ptrXoQzbxasXvQpMzcz",
  "PfLgJrSFmib" }
Returns: 9

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8563

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=11150&pm=8563

Writer:

mateuszek

Testers:

PabloGilberto , Olexiy , lovro , ivan_metelsky

Problem categories:

Brute Force, Simple Search, Iteration