# PROBLEM LINKS

Practice

Contest

# 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.

asked
**14 May '13, 15:16**

1★gamabunta

2.4k●128●183●169

accept rate:
14%