TopCoder problem "Teaching" used in SRM 427 (Division II Level Three)



Problem Statement

    

A language teacher in Antarctica wants his students to be able to read as many words as possible. However, he only has time to teach them K letters. After that, the students will only be able to read words containing only those K letters. Your task is to determine which K letters should be taught to maximize the number of words that the students will be able to read.



The Antarctican language is famous because it only contains words that start with "anta" and end with "tica" (quotes for clarity only). You are given a String[] words containing all the words in the language. Return the maximum number of words the students will be able to read if they learn the optimal set of K letters.

 

Definition

    
Class:Teaching
Method:count
Parameters:String[], int
Returns:int
Method signature:int count(String[] words, int K)
(be sure your method is public)
    
 

Constraints

-words will contain between 1 and 50 elements, inclusive.
-Each element of words will contain between 8 and 15 lowercase letters ('a'-'z').
-Each element of words will start with "anta" and end with "tica" (quotes for clarity).
-All elements of words will be distinct.
-K will be between 0 and 26, inclusive.
 

Examples

0)
    
{"antarctica","antahellotica","antacartica"}
6
Returns: 2
If you choose the letters a, c, i, n, t and r, students will be able to read the first and last words.
1)
    
{"antaxxxxxxxtica","antarctica"}
3
Returns: 0
No word in the Antarctican language contains 3 or fewer distinct letters.
2)
    
{"antabtica","antaxtica","antadtica","antaetica","antaftica",
 "antagtica","antahtica","antajtica","antaktica"}
8
Returns: 3

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13518&pm=10044

Writer:

rasto6sk

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Brute Force, Simulation, String Manipulation