Connection Status:
Competition Arena > SuperString

SuperString

SRM 259 · 2005-08-22 · by Andrew_Lazarev

SRM 259 · 2005-08-22 · by Andrew_Lazarev · Dynamic Programming, String Manipulation
Class Name: SuperString
Return Type: String
Method Name: goodnessSubstring
Arg Types: (vector<string>)
Problem Statement

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.

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"
4)
{"AK","A","E","J","C"}
Returns: "KAEJC"

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

Coding Area

Language: C++17 · define a public class SuperString with a public method string goodnessSubstring(vector<string> superstring) · 97 test cases · 2 s / 256 MB per case

Submitting as anonymous