### PROBLEM LINK:

**Author:** Sergey Kulik

**Tester:** Harshil Shah

**Editorialist:** Pawel Kacprzak

### DIFFICULTY:

CAKEWALK

### PREREQUISITES:

Strings, Implementation

### PROBLEM:

For a fixed set of Latin letters **S**, for each of given **N** words decide if it can be formed using only letters from **S**.

### QUICK EXPLANATION:

For each of given words, check if all its letters are in the given set of known letters **S** by iterating over letters in **S** explicitly or using any data structure with fast lookup operation.

### EXPLANATION:

## Subtask 1

In the first subtask, the set **S** contains exactly one letter. In this case, it is very easy to decide if a given word can be formed using only letters from **S**, because there is only one letter that can be used, so for example if the letter in **S** is **c**, then all possible words that can be written using it are: **c, cc, ccc, …**. Since the length of any word in the input can be at most 12, then there are exactly 12 different words for which the answer is `"Yes"`. For all other words the answer is `“No”`, because each of them contains at least one letter not in **S**.

## Subtask 2

In the second subtask, **S** can contain at most 26 letters. In this case, for a given input word **W**, we want to check if all its letters are in **S**. In order to do that, we can iterate over all letters of **W** and for each one check if it is in **S**. Since **S** is very small, that check can be performed actually by iterating over all letters in **S** explicitly. The answer is `“Yes”` if all letters of **W** are in **S**, otherwise the answer is `“No”`. Thus, for a single word **W**, the answer can be computed in **O(|W| * |S|)** time, so the total running time is **O(|total\_len|*|S|)**, where **total\_len** is the sum of lengths of all **N** words in the input.

For a faster solution, first we can store letters from **S** in any data structure that provides fast lookup - array will work the best here, since there are at most 26 different letters, but hash table is also fine here. If array is used this step building the array takes **O(|S|)** time. Then, for a given input word **W**, we can check if all of its letters are in **S** using the lookup in our data structure. It follows that the total running time of this method is **O(|S|+|total_len|)**, where **total_len** is the sum of lengths of all **N** words in the input.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Tester's solution can be found [here][333]. Editorialist's solution can be found [here][444].