TopCoder problem "WordsPuzzle" used in TCHS SRM 60 (Division I Level One)



Problem Statement

    

Vasya found a new game and he wants to try it out alone before playing it with his friends. The game consists of a String mainWord, a String[] secretWords and a String[] optionalWords. Each word from optionalWords can be used to replace a letter of mainWord.

The goal of the game is to replace at most two letters of mainWord with words from optionalWords in order to obtain a new word that contains the maximum possible number of words from secretWords as substrings. All replacements must happen simultaneously and only on letters of the original word. Each word from optionalWords can be used at most once.

Please help Vasya and return the maximal number of words from secretWords that can be found as substrings within a string obtained in the described way.

 

Definition

    
Class:WordsPuzzle
Method:countSecretWords
Parameters:String, String[], String[]
Returns:int
Method signature:int countSecretWords(String mainWord, String[] secretWords, String[] optionalWords)
(be sure your method is public)
    
 

Constraints

-mainWord will contain between 1 and 15 characters, inclusive.
-Each character of mainWord will be an uppercase letter ('A'-'Z').
-secretWords will contain between 1 and 8 elements, inclusive.
-Each element of secretWords will contain between 1 and 23 characters, inclusive.
-Each character of each element of secretWords will be an uppercase letter ('A'-'Z').
-All elements of secretWords will be distinct.
-optionalWords will contain between 1 and 8 elements, inclusive.
-Each element of optionalWords will contain between 1 and 5 characters, inclusive.
-Each character of each element of optionalWords will be an uppercase letter ('A'-'Z').
-All elements of optionalWords will be distinct.
 

Examples

0)
    
"HHHHH"
{"UUUU"}
{"UU"}
Returns: 0
Each word from optionalWords can be used in at most one replacement.
1)
    
"XYZ"
{"ABC", "PIO", "BCKP", "RT"}
{"ART", "KPIO", "ABCD"}
Returns: 2
In this case, we can fix any two letters of mainWord and replace them with words "ART" and "ABCD", getting "ABC" and "RT" as substrings.
2)
    
"U"
{"A", "B", "C"}
{"AAA", "BC"}
Returns: 2
Note that you should count the number of words that occur as substrings, not the total number of occurrences. So string "BC" is preferrable to string "AAA" (the first string contains two words "B" and "C", while the second one contains only one word "A").
3)
    
"ABCDXJKLMNOYUVW"
{"ABCD", "DEFG", "GHIJKLM", "NOPQ", "QRST", "TUVW", "JKLMNOPQR", "ABCDEFGHIJKLMNOPQRSTUVW"}
{"EFGHI", "PQRST", "EWQVG", "YHNJQ", "UTAPP", "JJJMK", "IOIIO", "LLALL"}
Returns: 8
If you replace 'X' with "EFGHI" and 'Y' with "PQRST", you will get the string which contains each word from secretWords as a substring.
4)
    
"BJFDIJEBHBGICCF"
{"DG", "BGAC", "GBD", "E", "GFEDI", "J", "JEFD", "HHJB"}
{"ICID", "A", "HB", "E", "BABE", "F", "FH", "DC"}
Returns: 3
5)
    
"QXRVYNI"
{"QX", "XR", "RV", "VY", "YN", "YNI", "QXR", "RVY"}
{"ACACA", "BDB"}
Returns: 8
No letter of mainWord should be replaced.
6)
    
"PLMOKNIJB"
{"ALMOKNIJB", "KNIJB"}
{"A", "X", "Y", "Z"}
Returns: 2
7)
    
"GHJKLBNM"
{"XYZW", "PWREQ", "LKATRRQ", "XPMNYTR", "QWWQ", "GHJCLBNM"}
{"WWWW", "QQQQQ", "QWEQE", "C", "Y"}
Returns: 1

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13529&pm=10042

Writer:

boba5551

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Simple Search, Iteration, String Manipulation