Spring 2003, Weekly Problem 7

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2002, TopCoder, Inc. All rights reserved.


Problem Statement

If you want to write a message anonymously, one way to do it is to cut out letters from headlines in a newspaper and paste them onto a blank piece of paper to form the message you want to write. Given several headlines that you have cut out, determine how many messages from a list you can write using the letters from the headlines. You should only consider each message by itself and not in conjunction with the others, see example 2.

Create a class Anonymous which contains the method howMany which takes as parameters a tvector<string> headlines containing the headlines which you have cut out as well as a tvector<string> messages with the messages you may want to write, and returns an int which is the total number of messages you can write.

Definition

(be sure your method is public)

Class

#include <string> using namespace std; #include "tvector.h" class Anonymous { public: int howMany(const tvector <string>& headlines, const tvector <string>& messages) { // fill in code here } };

Notes and Constraints

Examples

  1. headlines =
    
    {"Earthquake in San Francisco",
     "Burglary at musuem in Sweden",
     "Poverty"}
    
    messages =
    
    {"Give me my money back",
     "I am the best coder",
     "TOPCODER"}
    
    Returns: 2

    In the first message we have three 'm's, but there are only two 'm's among the headlines (both in the word "museum"), so this message can't be written.

    The second message can be written. Note that the first letter, 'I', only appears as lower case in the headlines, but that's allowed. The last message can also be written, so the method should return 2.

  2. headlines = 
    
            {"Programming is fun"}
    
    messages = 
    
            {"program","programmer","gaming","sing","NO FUN"}
    
    Returns: 4

    The messages "program", "gaming", "sing" and "NO FUN" can all be written but not "programmer" (no 'e's exist). The method should return 4.

  3. headlines = 
    
       {"abcdef","abcdef"}
    
    messages = 
    
       {"AaBbCc","aabbbcc","   ","FADE"}
    
    Returns: 3

    All messages except the second one can be written, because it contains three 'b's but there are only two 'b's available. Also note the message only containing spaces - such a message can of course always be written.


Owen L. Astrachan
Last modified: Wed Jul 23 10:31:04 EDT 2003