TopCoder problem "ReadingBooks" used in SRM 404 (Division II Level One)



Problem Statement

    

There are some books, each consisting of exactly three parts: introduction, story and edification. There is a reader who goes through the books and reads various parts. Each time he finishes reading a part, he adds the name of the part to the end of a list. He may read zero or more parts from each book, and he can read them in any order, but he cannot read each part more than once. Whenever he starts reading a new book, he can no longer go back and read any parts of books he has looked at previously.

You are given a String[] readParts containing the list created by the reader. Each element of readParts is "introduction", "story" or "edification" (quotes for clarity). Return the maximum possible number of books for which the reader has read all three parts.

 

Definition

    
Class:ReadingBooks
Method:countBooks
Parameters:String[]
Returns:int
Method signature:int countBooks(String[] readParts)
(be sure your method is public)
    
 

Constraints

-readParts will contain between 1 and 50 elements, inclusive.
-Each element of readParts will be "introduction", "story" or "edification" (quotes for clarity).
 

Examples

0)
    
{"introduction", "story", "introduction", "edification"}
Returns: 1
It is possible that the reader has read the introduction from the first book and all 3 parts from the second one. Of course, it is also possible that he has read one part from four different books, but we are interested in the maximal number of books for which all 3 parts have been read.
1)
    
{"introduction", "story", "edification", "introduction", "story", "edification"}
Returns: 2
Two books have been read in their entirety.
2)
    
{"introduction", "story", "introduction", "edification", "story", "introduction"}
Returns: 1
3)
    
{"introduction", "story", "introduction", "edification", "story",
 "story", "edification", "edification", "edification", "introduction",
 "introduction", "edification", "story", "introduction", "story",
 "edification", "edification", "story", "introduction", "edification",
 "story", "story", "edification", "introduction", "story"}
Returns: 5

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8216

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12176&pm=8216

Writer:

boba5551

Testers:

PabloGilberto , Yarin , Olexiy , ivan_metelsky

Problem categories:

Greedy, Simple Search, Iteration