Problem Statement

You are going to make a fruit birthday cake for a party. There are several kinds of fruit you can choose from, and you must choose at least K different kinds to put on the cake. However, some of your friends don't like certain kinds of fruits, and they will refuse to eat a cake containing any of those fruits. You want as many of your friends as possible to eat the cake.

You are given a String[] availableFruits, where each element is a kind of fruit that you can put on the cake. You are also given a String[] friendsDislikings, where each element is a space-separated list of the kinds of fruits that one of your friends doesn't like. Return the largest number of friends that can eat the cake, assuming that you must use at least K different kinds of fruits.

Definition

 Class: BirthdayCake Method: howManyFriends Parameters: String[], String[], int Returns: int Method signature: int howManyFriends(String[] availableFruits, String[] friendsDislikings, int K) (be sure your method is public)

Constraints

-availableFruits will contain between 1 and 50 elements, inclusive.
-Each element of availableFruits will contain between 1 and 50 characters, inclusive.
-Each element of availableFruits will contain only lowercase letters ('a' - 'z').
-All elements of availableFruits will be distinct.
-friendsDislikings will contain between 1 and 20 elements, inclusive.
-Each element of friendsDislikings will contain between 1 and 50 characters, inclusive.
-Each element of friendsDislikings will be a space-separated list of fruit names without any leading or trailing spaces.
-Each fruit name in each element of friendsDislikings will consist of lowercase letters ('a' - 'z') only.
-Fruit names in each element of friendsDislikings will all be distinct.
-K will be between 1 and the number of elements in availableFruits, inclusive.

Examples

0)

 `{ "apple", "orange", "strawberry", "cherry" }` `{ "apple orange", "apple cherry", "strawberry orange", "cherry", "apple" }` `2`
`Returns: 3`
 You can make your cake using strawberries and oranges and friends 1, 3 and 4 (0-based) will eat it.
1)

 `{ "strawberry", "orange", "apple", "lemon", "watermelon" }` `{ "orange", "apple", "lemon", "watermelon" }` `1`
`Returns: 4`
 A strawberry cake is a perfect match here.
2)

 `{ "apple", "orange" }` `{ "strawberry" }` `2`
`Returns: 1`
 Note that friends may dislike a fruit you don't even have.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13513&pm=10036

mateuszek

Testers:

PabloGilberto , Olexiy , ivan_metelsky , ged

Problem categories:

Brute Force, String Manipulation, String Parsing