NAME1 - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

CAKEWALK

PREREQUISITES

Ad-Hoc

PROBLEM

You are given two strings A and B. You are also given N strings C1, C2, … CN.

Let C = C1 + C2 + … CN
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.

1 Like