TopCoder problem "StringInterspersal" used in SRM 414 (Division I Level Two)



Problem Statement

    

A String S is an interspersal of a set of Strings W, if W is a set of disjoint subsequences of S which cover S. Less formally, S can be formed from W by partitioning each member of W into substrings, then concatenating all the substrings, while maintaining the order of the substrings within each element of W. For example, if W contains the strings {"DESIGN", "ALGORITHM", "MARATHON"}, then one possible interspersal would be "ADELGMAORARISIGNTHMTHON", formed as shown below.



 DE         SIGN

A  LG  O  RI    THM

     MA RA         THON

-----------------------

ADELGMAORARISIGNTHMTHON

Given a String[] W, return the lexicographically minimum interspersal of the Strings in W

 

Definition

    
Class:StringInterspersal
Method:minimum
Parameters:String[]
Returns:String
Method signature:String minimum(String[] W)
(be sure your method is public)
    
 

Notes

-The lexicographically minimum of two Strings is the one with the alphabetically earlier character at the first position at which they differ.
-The return String will contain no more than 1000 characters.
 

Constraints

-W will contain between 1 and 20 elements, inclusive.
-Each element of W will contain between 1 and 50 uppercase letters ('A'-'Z'), inclusive.
 

Examples

0)
    
{"DESIGN","ALGORITHM","MARATHON"}
Returns: "ADELGMAORARISIGNTHMTHON"
The example from the problem statement.
1)
    
{"TOMEK","PETR","ACRUSH","BURUNDUK","KRIJGERTJE"}
Returns: "ABCKPERIJGERRTJETOMEKTRURUNDUKUSH"
2)
    
{"CCCA","CCCB","CCCD","CCCE"}
Returns: "CCCACCCBCCCCCCDE"
3)
    
{"BKSDSOPTDD","DDODEVNKL","XX","PODEEE","LQQWRT"}
Returns: "BDDKLODEPODEEEQQSDSOPTDDVNKLWRTXX"
4)
    
{"TOPCODER","BETFAIR","NSA","BT","LILLY"}
Returns: "BBELILLNSATFAIRTOPCODERTY"
5)
    
{"QITHSQARQV","BYLHVGMLRY","LKMAQTJEAM","AQYICVNIKK","HKGZZFFEWC"}
Returns: "ABHKGLKMAQIQQTHSQARQTJEAMVYICVNIKKYLHVGMLRYZZFFEWC"
6)
    
{"XHCYBTUQUW","EKBISADSSN","LOOISPOFAK","MIXBDHPJUQ","BNMNDHMOTC"}
Returns: "BEKBILMINMNDHMOOIOSADSPOFAKSSNTCXBDHPJUQXHCYBTUQUW"

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13505&pm=8772

Writer:

StevieT

Testers:

PabloGilberto , Olexiy , gawry , ivan_metelsky

Problem categories:

Greedy, String Manipulation