StringInterspersal

SRM 414 · 2008-08-16 · by StevieT

SRM 414 · 2008-08-16 · by StevieT · Greedy, String Manipulation

Show categories

Class Name: StringInterspersal

Return Type: String

Method Name: minimum

Arg Types: (vector<string>)

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

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

{"DESIGN","ALGORITHM","MARATHON"}
Returns: "ADELGMAORARISIGNTHMTHON"

The example from the problem statement.

{"BA","B","BA","B","BA"}
Returns: "BABABABB"

{"TOMEK","PETR","ACRUSH","BURUNDUK","KRIJGERTJE"}
Returns: "ABCKPERIJGERRTJETOMEKTRURUNDUKUSH"

{"CCCA","CCCB","CCCD","CCCE"}
Returns: "CCCACCCBCCCCCCDE"

{"BKSDSOPTDD","DDODEVNKL","XX","PODEEE","LQQWRT"}
Returns: "BDDKLODEPODEEEQQSDSOPTDDVNKLWRTXX"

Submissions are judged against all 129 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class StringInterspersal with a public method string minimum(vector<string> W) · 129 test cases · 2 s / 256 MB per case