### PROBLEM LINKS

### DIFFICULTY

CAKEWALK

### PREREQUISITES

Ad-Hoc

### PROBLEM

You are given two strings **A** and **B**. You are also given **N** strings **C _{1}**,

**C**, …

_{2}**C**.

_{N}Let **C = C _{1} + C_{2} + … C_{N}**

where

**+**is the

**concatenation**

**operator**(note that it is

**not**

**commutative**)

Find whether **C** may be a substring of one of the permutations of **A + B**.

### QUICK EXPLANATION

The length of **A + B** can be **80000**. Of course, we cannot possibly generate all the permutations of **A + B**. Let us use some insight.

Lemma: If **C** is a substring of a permutation of **A + B**, then there is a permutation of **A + B** in which **C** is a prefix.

It is easy to see that if **C** exists as a substring, we can shift all the characters on the left of the first occurance of **C**, to the end of the string without affecting the presence of **C** in the permutation of **A + B**. Also, if **C** is a prefix of some permutation of **A + B**, then it is also a permutation which is proof enough to return a positive answer.

Lemma: If there is no permutation of **A + B** such that **C** is a prefix, then there is no permutation of **A + B** such that **C** is a substring.

This is easily proven by contradiction. If we assume that there is a permutation of **A + B** in which **C** is a substring, then by the previous Lemma we should have a permutation of **A + B** in which **C** is a prefix. Thus our assumption cannot be true.

From the above two, we can clearly say

**C** can be a substring of some permutation of **A + B** iff there is a permutation of **A + B** of which **C** is a prefix.

### EXPLANATION

Since we have the liberty to assume any permutation of **A + B**, we can treat it as a bag of characters and just try to build a permutation with **C** as prefix. If we are unable to, then of course we return negative. Otherwise, we can successfully have **C** as a substring by letting the other characters occupy any position on the left or right of the constructed string **C** (from characters in **A + B**).

We can build a count of all the characters in **A + B** as follows

counts[a ... z] = { 0 } for each character c in A counts[c]++ for each character c in B counts[c]++

We can construct **C** by concatenating the given strings. The statement assures us that the length of **C** is not more than the length of **A + B**. Then we can one by one reduce the count of the characters in **C**. If any of the counts become negative, then we know that we cannot choose that character and that **C** cannot exist as a prefix (as well as substring) of any permutation of **A + B**.

for each chatacter c in C counts[c]-- if counts[c] < 0 return false return true

The complexity of the algorithm is **O(|A| + |B| + |C|)**.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.