PROBLEM STATEMENT
Mike, Chuck, Dok, and Gt494 are in a band - 4 of their albums have gone
platinum. Now they want to make a greatest hits album. However, they want to
order the tracks on their greatest hits album in such a way that their most
loyal fans can find their favorite track very easily. They want to put as many
tracks as they can in the same track number as in the original CD they had.
For example, the song "Ironman" was track #2 on their debut album, so if
possible, they would like for it to be track #2 on their greatest hits album.
Write a function that given a String[] of albums, and a String of the tracks
that will appear on their greatest hits CD, returns the maximum number of
tracks that can have the same track number on the greatest hits CD as on the CD
in which they originally appeared. Note that there may be more than one way to
achieve this maximum, i.e. two orderings may both have 3 tracks in the correct
place (see example 1).
DEFINITION
Class Name: Greatest
Method Name: maxSamePos
Parameters: String[], String
Returns: int
Method signature (be sure your method is public): int maxSamePos(String[]
albums, String greatestHits);
TopCoder will check the validity of inputs. Inputs are valid if all the of the
following are true:
- albums will contain between 0 and 10 elements.
- each element of albums will contain between 1 and 50 characters, inclusive.
- Each element of albums will be formatted as follows: "<Track1> <Track2>
<Track3> ... <Trackn>". Quotes, angle brackets and "..." are just for clarity,
they will not be included. Each element will contain no leading or trailing
spaces.
- greatestHits will be formatted as follows: "<Track> <Track> <Track> ...
<Track>". Quotes, angle brackets and "..." are just for clarity, they will not
be included. Each element will contain no leading or trailing spaces.
- greatestHits will contain between 0 and 50 characters, inclusive.
- Each track appearing in greatestHits appears in exactly one element of
albums.
- No track may appear more than once on the same album.
- No track may appear on more than one album.
- There will be between 1 and 24 (inclusive) tracks in each element of albums.
- There will be between 0 and 24 (inclusive) tracks in greatestHits.
- Each element of albums may contain only the characters 'A'-'Z', 'a'-'z',
'0'-'9' and the space character (' ').
NOTES
* Within each element of albums, the order in which the tracks appear in the
String is the order in which they appeared on the album. So the first entry in
the String corresponds to the first track of that album, etc.
* All elements of albums will not necessarily have the same number of tracks.
* Tracks are case-sensitive so "Ironman" and "ironman" are different.
* There may be zero tracks in greatestHits.
* All songs appearing in greatestHits must appear on the greatest hits album.
* Only songs appearing in greatestHits may appear on the greatest hits album.
No songs not on greatestHits may be added, and no blank tracks may be added.
The number of tracks on the greatest hits album will be exactly the number of
entries in greatestHits.
EXAMPLES
1. albums = {"Registration Ironman ChallengePhase CodingPhase",
"NDBronson dmwright qubits ZorbaTHut",
"SubmissionAccuracy ConsecutiveWins AllTimeWins",
"RoundTables BugsAndAnnoyances EvolvingStrategy"}
greatestHits = "Ironman NDBronson AllTimeWins RoundTables"
If the greatest hits album is ordered "RoundTables Ironman AllTimeWins
NDBronson", then the first three tracks on the greatest hits album all appear
in the same track as on their original albums. Your method should return 3.
Note that the ordering is not necessarily unique, i.e. "NDBronson Ironman
AllTimeWins RoundTables" also has three tracks in the same place.
2. albums = {"A B C D E F G",
"a b c d e",
"1 2 3 4 5 6 7 8 9"}
greatestHits = "3 1 d C 9 8 a G 2"
If the greatestHits album is ordered "1 2 C d 3 a G 8 9" then 1, 2, C, d, G,
8 and 9 are all on the same track number as on their original album. Your
method should return 7.
3. albums = {"ThisSongSucks"}
greatestHits = ""
There are no songs on the greatestHits CD. Your method should return 0.