JOIN
Get Time

   Problem Statement  

 Problem Statement for StringInterspersal

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"

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 414 Round 1 - Division I, Level Two