UnknownNames | Topcoder Archive

Problem Statement

You are given a String[] questionMarkNames, where each element represents a single name, and all names have the same length. Some of the letters are missing, and those letters are represented by question marks ('?'). Arrange the names in a vertical row, such that corresponding characters in each name are in the same column. Then, order the names so that each column is sorted in non-decreasing order from top to bottom. You can replace each question mark with any letter to achieve this.

Return a String[] containing the lexicographically earliest ordering that you can achieve. If there is no way to achieve the goal, return an empty String[] instead. An ordering A comes before an ordering B if A contains an alphabetically earlier name at the first index where they differ.

Definition

Class:: UnknownNames
Method:: sortNames
Parameters:: String[]
Returns:: String[]
Method signature:: String[] sortNames(String[] names)
(be sure your method is public)

Constraints

questionMarkNames will contain between 2 and 50 elements, inclusive.
Each element of questionMarkNames will containt between 1 and 50 characters, inclusive.
All elements of questionMarkNames will be of the same length.
Each character of each element of questionMarkNames will be an uppercase letter ('A'-'Z') or a question mark ('?').

Examples

```
{"?ED?", "TO??", "????"}
```
```
Returns: {"AAAA", "AEDA", "TODA" }
```
If we make the order of names 0 1 2 then the lexicographically earliest ordering is AEDA TODA TODA 0 2 1 AEDA AEDA TOEA 1 0 2 TO?? TED? T??? - IMPOSSIBLE for this order, because O is after E, etc.

{"T???????", "SO??????", "?MP?????", "??OC????", "???BO???", "????MD??", "?????CE?", "??????CR"}

Returns: {"AAAAAACR", "AAAAACER", "AAAAMDER", "AAABODER", "AAOCODER", "AMPCODER", "SOPCODER", "TOPCODER" }

{ "?E", "L?", "??", "L?"}

Returns: {"AA", "AE", "LE", "LE" }

{"A???J?", "BC????", "?DE???", "??FG??", "???HI?"}

Returns: { }

{"AAH????AB?EE??GCB?HE?G?CACA?A?B??A?JG?AGD????F?EEE",
 "?D?NI??JK?H?N?K???HKM?L?GE?N??G?K?L??M?HM??CP?E?NJ",
 "?KOVL?????K??TKP???L??N?N??O????MI?Y?QK?NR?E?RF???",
 "?M?Z??N?T??R????????TP?OQ??SY??Z?O?Z?YTL?RMG???YV?",
 "W???????Z?TX?Z???XZMYRNX??L??Q?????????L?T?J????Z?",
 "ZYZZ?????S?ZZZ?Z??ZV?Y????LZ?R?ZZVZZ?Z??ZT?M?V?Z??",
 "?Y?Z?Z?X??UZ?ZZ??ZZY?ZV?Z?MZ?W?Z??Z?ZZ?????TZ??Z?Z",
 "Z?????Z??ZV????Z????Z?????S????ZZZZ????Z???TZ?W?ZZ",
 "ZZ??ZZZ???WZZZ????Z?Z?Z?Z???Z?Z?ZZ?Z??Z??Z?W???ZZ?",
 "??????????Z?Z?Z??Z?ZZZ?Z??ZZ?Z?????ZZ??ZZZZZ??ZZ??",
 "?Z?Z???Z????Z?ZZ??Z?ZZZ?Z???Z?ZZ??Z?Z??Z??Z??Z???Z",
 "?Z?ZZ?Z??ZZ?ZZ???????Z???ZZZ?Z?ZZ?Z?ZZ?Z?ZZZ?Z??ZZ",
 "??Z??ZZ?Z?ZZ?ZZ????Z???Z??Z???????Z??Z??Z???Z?ZZ?Z",
 "ZZ??Z?ZZ??ZZZ??Z????ZZ?Z?ZZ??ZZ???Z?ZZ??ZZZZZZZ??Z",
 "?Z????ZZZ???Z??Z?Z?Z?Z????Z??ZZZZ??ZZ?Z?????Z??Z??",
 "Z???ZZZ??Z?ZZ??Z??Z?Z???Z???ZZ??Z???Z?ZZ??ZZ??Z??Z",
 "??????ZZ???Z?Z?ZZ?ZZ????Z??Z??????ZZ?ZZ?Z?Z?Z??Z??",
 "ZZZ?Z??ZZ???Z??Z?Z?ZZ?Z??ZZ?Z????ZZZ??Z??Z?ZZ??ZZZ",
 "Z?Z???ZZZ???ZZ?Z??Z???ZZZZZ??Z??Z??Z?Z?ZZZ?ZZ??Z?Z",
 "Z???Z???ZZ?Z??Z??ZZ??ZZZ??Z??ZZ?Z?????????Z???Z?ZZ",
 "Z?Z????Z?ZZZ?????Z???Z?Z??ZZ??Z??ZZZ??ZZZ?Z?ZZ?Z?Z",
 "???Z?????????ZZZZ??Z?Z??Z????Z??ZZ???Z?ZZ??????Z??",
 "???Z?Z?ZZZ?Z??Z?????Z??????ZZZ?Z?Z?ZZ?ZZZZZ?ZZZZ??",
 "Z??ZZ??Z?????Z????ZZZ?Z?Z??Z?ZZZ?Z?Z???Z?Z??????Z?",
 "ZZ?Z?ZZ?Z???ZZ????Z???Z?Z??Z?ZZZZ??ZZZ???ZZ?Z?ZZZ?",
 "??ZZ????ZZ??Z?Z????ZZZ?Z?Z?Z?ZZZ?Z???ZZ?ZZ???Z???Z",
 "Z??Z???Z?ZZZ???Z?Z?????Z???ZZ???Z?ZZZ?????Z??ZZZ??",
 "?Z????ZZZ??Z???????Z???Z???Z?Z?Z??Z?ZZ?ZZ?ZZZZ???Z",
 "?ZZZ?ZZZZ?ZZ?Z?ZZZZ?ZZ?Z?Z??Z?ZZ??ZZ?Z???Z??????ZZ",
 "ZZ?ZZZ??Z????Z?ZZZZZ?Z???Z??ZZ?Z???ZZ?Z?Z?ZZ??ZZZZ",
 "?ZZ?Z?ZZ?ZZZ?ZZ??ZZZZ?ZZ?Z?Z?????ZZ???ZZZZ?Z?Z?ZZ?",
 "Z??ZZ??ZZ???Z?ZZZ??Z??ZZ?Z?Z??????Z?ZZ?ZZZZ?Z?Z??Z",
 "???ZZ???ZZZZZZ???????ZZZZZ?Z?Z?ZZZZZ??ZZZ??ZZZ????",
 "Z?ZZ?Z?ZZ???ZZZZZ???ZZ?ZZ?Z??ZZ?Z????Z??Z?????ZZ?Z",
 "??Z?ZZZ?Z???Z???Z?ZZ???Z??ZZ???Z??ZZ??Z???Z?????ZZ",
 "?Z?Z?Z?Z?Z?Z?ZZ???Z??ZZ?ZZZ?Z???????Z?ZZ?ZZ???????",
 "Z??Z??Z???ZZZZZZ??ZZ???????ZZZZ?Z?????ZZ?Z??Z??ZZ?",
 "????????Z??ZZ????ZZ??Z?ZZ???Z?ZZ??Z?Z??ZZZ?ZZZ?ZZ?",
 "??Z??ZZ?Z?Z?????Z??Z?ZZZ??Z?Z?ZZ??ZZ?Z?Z?ZZ???ZZ??",
 "??ZZ???ZZ????????ZZZZ????Z??ZZ?Z?Z?ZZZZZZZ????ZZ??",
 "?ZZ?Z????ZZ???ZZZ?Z???Z?ZZZ???Z?ZZZ?????ZZZZZ?Z?ZZ",
 "????Z?Z??Z????Z??ZZZZZ??Z??ZZZ?ZZ??Z???Z?Z?Z???ZZ?",
 "Z???????Z?ZZZZ??Z?ZZZ?ZZZ??Z??Z??Z?Z?ZZZ?Z?Z?ZZ?ZZ",
 "?Z?ZZ??ZZZZ???ZZZZZZZ?ZZ????Z?Z?ZZ???Z?Z?ZZ???Z??Z",
 "??Z?Z??Z?Z??ZZ??Z?ZZ?Z???ZZ??ZZ???Z?????Z?Z?ZZ?Z?Z",
 "Z?Z??ZZ???ZZ?ZZZ?ZZZ??Z????ZZ???ZZ?ZZ????ZZ???ZZZ?",
 "????ZZ?ZZ?ZZ?ZZ??ZZZ???ZZZ??Z???Z??ZZ?Z?????Z????Z",
 "??ZZ?Z??Z?ZZ???ZZ?Z?Z?Z?????Z?Z???Z??ZZ??Z?Z?ZZ??Z", 
 "?ZZZZ??Z?Z?ZZZ?Z?Z?Z?ZZZ???Z??Z?ZZ??Z?Z??Z??Z?Z??Z",
 "ZZ?Z???Z??ZZZ?ZZZ?ZZ?ZZ?ZZ???ZZZZ?Z??Z?Z?Z?Z??Z??Z"}

Returns: {"AAHAAAAABAEEAAGCBAHEAGACACAAAABAAAAJGAAGDAAAAFAEEE", "ADHNIAAJKAHENAKCBAHKMGLCGEANAAGAKALJGMAHMAACPFEENJ", "AKOVLAAJKAKENTKPBAHLMGNCNEAOAAGAMILYGQKHNRAEPRFENJ", "AMOZLANJTAKRNTKPBAHLTPNOQEASYAGZMOLZGYTLNRMGPRFYVJ", "WMOZLANJZATXNZKPBXZMYRNXQELSYQGZMOLZGYTLNTMJPRFYZJ", "ZYZZLANJZSTZZZKZBXZVYYNXQELZYRGZZVZZGZTLZTMMPVFZZJ", "ZYZZLZNXZSUZZZZZBZZYYZVXZEMZYWGZZVZZZZTLZTMTZVFZZZ", "ZYZZLZNXZSUZZZZZZZZZYZVXZEMZYZGZZZZZZZTZZTMTZVFZZZ", "ZYZZLZNXZZUZZZZZZZZZZZVZZZMZYZZZZZZZZZZZZZMTZZFZZZ", "ZYZZLZZXZZVZZZZZZZZZZZVZZZSZYZZZZZZZZZZZZZMTZZWZZZ", "ZYZZLZZZZZVZZZZZZZZZZZVZZZSZYZZZZZZZZZZZZZZTZZWZZZ", "ZYZZLZZZZZVZZZZZZZZZZZVZZZSZZZZZZZZZZZZZZZZTZZZZZZ", "ZYZZLZZZZZVZZZZZZZZZZZVZZZSZZZZZZZZZZZZZZZZTZZZZZZ", "ZYZZLZZZZZVZZZZZZZZZZZVZZZZZZZZZZZZZZZZZZZZTZZZZZZ", "ZYZZZZZZZZVZZZZZZZZZZZVZZZZZZZZZZZZZZZZZZZZTZZZZZZ", "ZYZZZZZZZZVZZZZZZZZZZZVZZZZZZZZZZZZZZZZZZZZTZZZZZZ", "ZYZZZZZZZZVZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZTZZZZZZ", "ZYZZZZZZZZVZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZTZZZZZZ", "ZYZZZZZZZZVZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZTZZZZZZ", "ZZZZZZZZZZVZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZTZZZZZZ", "ZZZZZZZZZZVZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZTZZZZZZ", "ZZZZZZZZZZVZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZTZZZZZZ", "ZZZZZZZZZZVZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZTZZZZZZ", "ZZZZZZZZZZVZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZTZZZZZZ", "ZZZZZZZZZZWZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZWZZZZZZ", "ZZZZZZZZZZWZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ", "ZZZZZZZZZZWZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ", "ZZZZZZZZZZWZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ", "ZZZZZZZZZZWZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ", "ZZZZZZZZZZWZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ", "ZZZZZZZZZZWZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ", "ZZZZZZZZZZWZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ", "ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ", "ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ", "ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ", "ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ", "ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ", "ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ", "ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ", "ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ", "ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ", "ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ", "ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ", "ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ", "ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ", "ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ", "ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ", "ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ", "ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ", "ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ" }

```
{"BI", "AQ"}
```
```
Returns: { }
```

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)2024, Topcoder, Inc. All rights reserved.