WordSplit

TCO07 Sponsor 2 · 2007-03-07 · by dgoodman

TCO07 Sponsor 2 · 2007-03-07 · by dgoodman · Dynamic Programming

Show categories

Class Name: WordSplit

Return Type: String[]

Method Name: pieces

Arg Types: (string)

Problem Statement

Given a string of lowercase letters, I want to split it up into pieces so that the letters in each piece are distinct. I want to form as few pieces as possible. Given theString return a String[] containing the pieces sorted alphabetically.

If more than one way of splitting is minimal, return the sorted sequence of pieces that is first lexicographically. That means that the first element in the sequence that differs is earlier alphabetically.

Constraints

theString will contain between 1 and 50 characters, inclusive.
Each character in theString will be a lowercase letter ('a'-'z').

Examples

"facetiously"
Returns: {"facetiously" }

No splits are required since all the letters are distinct.

"aaaaa"
Returns: {"a", "a", "a", "a", "a" }

This is the only legal split.

"aba"
Returns: {"a", "ab" }

We need one split to separate the 'a's. Our choices are a/ba or ab/a. We return the one whose pieces form the earlier sequence lexicographically.

"alabamaalleluiahalas"
Returns: {"a", "a", "a", "al", "al", "bam", "eluiah", "l", "las" }

"aaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaa"
Returns: {"a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "ab" }

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

Coding Area

Language: C++17 · define a public class WordSplit with a public method vector<string> pieces(string theString) · 178 test cases · 2 s / 256 MB per case