TopCoder problem "Mailbox" used in SRM 215 (Division II Level Two)

Problem Statement

We are going to sell a collection of individual plastic characters that customers will buy and place on their mailboxes to spell out their addresses. We have a String[] of "typical" addresses and want to be able to compare a proposed collection to these addresses and determine how many are impossible to form from our collection.

We will count an address as impossible if it cannot be formed from our entire collection of characters. Space characters in an address can always be formed because the customer can form spaces by placing our plastic characters as he wishes.

Create a class Mailbox that contains a method impossible that is given a String collection and a String[] address and that returns the number of elements in address that are impossible to form from the given collection of characters.

Definition

Class:	Mailbox
Method:	impossible
Parameters:	String, String[]
Returns:	int
Method signature:	int impossible(String collection, String[] address)
(be sure your method is public)

Constraints

collection will contain between 1 and 50 characters inclusive

Each character in collection will be an uppercase letter 'A'-'Z' or a digit '0'-'9'.

address will contain between 1 and 50 elements inclusive.

Each element of address will contain between 1 and 50 characters inclusive.

Each character in each element of address will be an uppercase letter 'A'-'Z' or a digit '0'-'9' or a space ' '.

Examples

"AAAAAAABBCCCCCDDDEEE123456789"

{"123C","123A","123 ADA"}

Returns: 0

All these can be formed. The space in "123 ADA" can never be a problem, and collection contains two 'A's. We only consider one address at a time so it doesn't matter that we cannot form both "123C" and "123A" at the same time from this collection.

"ABCDEFGHIJKLMNOPRSTUVWXYZ1234567890"

{"2 FIRST ST"," 31 QUINCE ST", "606 BAKER"}

Returns: 3

We cannot form any of these. The first address requires two 'S's, the second address requires a 'Q', and the third address requires two '6's.

"ABCDAAST"

{"111 A ST", "A BAD ST", "B BAD ST"}

Returns: 2

"111 A ST" cannot be formed since collection does not contain any digits. "B BAD ST" cannot be formed because it requires 2 'B's.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5861&pm=2884

Writer:

dgoodman

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Simple Search, Iteration, String Manipulation