Connection Status:
Competition Arena > AirportCodes

AirportCodes

SRM 816 · 2021-10-13 · by misof

SRM 816 · 2021-10-13 · by misof · Brute Force, Simple Search, Iteration, String Manipulation
Class Name: AirportCodes
Return Type: String[]
Method Name: name
Arg Types: (vector<string>)
Problem Statement

Problem Statement

There are some airports in the world. Each airport has a name. These names are given in the String[] airports.

It was now decided that each airport needs a three-letter code. The code for each airport must have two properties:

  • It must be possible to obtain the code from the name of the airport by erasing some characters of the name. (The three characters that remain must still be in their original order.)
  • There cannot be any other airport that could have this code.

Return a String[] with the same number of elements as airports. For each airport, in the order in which they were given, return either a valid three-letter code it can have, or an empty string if there is no valid code for this airport.

Notes

  • If there are multiple valid answers, any one of them will be accepted.

Constraints

  • airports will have between 1 and 30 elements, inclusive.
  • Each element of airports will have between 3 and 30 characters, inclusive.
  • Each character in airports will be an uppercase English letter ('A'-'Z').
Examples
0)
{"FRANKFURT", "ZURICH", "LONDONHEATHROW"}
Returns: {"FRA", "ZRH", "LHR" }

The returned airport codes have both desired properties. For example, you can produce "ZRH" from "ZURICH" by erasing 'U', 'I', and 'C'; and you cannot produce "ZRH" from either of the two other airport names.

1)
{"NEWYORK", "NEWJERSEY", "NEWPORT", "NEUSTADT"}
Returns: {"NEK", "NEJ", "NEP", "NEU" }

There are many valid answers. For example, "NEWYORK" could also get the code "NOK" or "ORK", while "NEWJERSEY" could also get the code "EEE".

2)
{"NEWYORK", "NEWYORK", "NEWARK"}
Returns: {"", "", "NEA" }

Someone was dumb enough to give two airports the same name. In this situation it is clearly impossible to give either of those two airports a valid code.

3)
{"ULM", "FEZ", "ELY", "JERUSALEM"}
Returns: {"", "FEZ", "ELY", "JER" }

While Fez and Ely can get valid codes, the only code we can assign to Ulm is "ULM", and that is not a valid code - it can also be obtained by erasing six of the nine letters in "JERUSALEM".

4)
{"AAAAAAAAA", "AAAAAAB", "ABAAAAAA", "ABA", "AAAAABABAAAAA", "AAAAAABBBBBBAAAAAA"}
Returns: {"", "", "", "", "BAB", "BBB" }

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

Coding Area

Language: C++17 · define a public class AirportCodes with a public method vector<string> name(vector<string> airports) · 42 test cases · 2 s / 256 MB per case

Submitting as anonymous