TopCoder problem "SuperString" used in SRM 259 (Division I Level Two)



Problem Statement

    

We define the goodness of a string S as the number of letters that appear in S only once. For instance, the goodness of the string "CHALLENGE" is 5 because it contains 5 distinct letters 'C', 'H', 'A', 'N' and 'G'.

You are given a String[] superstring. superstring is split for convenience only, so you should concatenate all of its elements in order and treat it as a single string. You are to find the substring of superstring that has the maximal goodness. In case of a tie, return the substring that comes earliest alphabetically.

 

Definition

    
Class:SuperString
Method:goodnessSubstring
Parameters:String[]
Returns:String
Method signature:String goodnessSubstring(String[] superstring)
(be sure your method is public)
    
 

Constraints

-superstring will have between 1 and 50 elements, inclusive.
-Each element of superstring will contain between 1 and 50 characters, inclusive.
-Each element of superstring will contain uppercase letters ('A'-'Z') only.
 

Examples

0)
    
{"CHALLENGE"}
Returns: "CHALLENG"
1)
    
{"THEWORD"}
Returns: "THEWORD"
2)
    
{"THE", "MULTI", "LINE", "TEST"}
Returns: "HEMULTI"
3)
    
{"ZYXWVUTSRQPONMLKJIHGFEDCBA", "ZYXWVUTSRQPONMLKJIHGFEDCBA"}
Returns: "AZYXWVUTSRQPONMLKJIHGFEDCB"

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8012&pm=4718

Writer:

Andrew_Lazarev

Testers:

PabloGilberto , lbackstrom , brett1479 , Olexiy

Problem categories:

Dynamic Programming, String Manipulation