PROBLEM LINK:
Author: Pavel Sheftelevich
Tester: Sergey Kulik
Editorialist: Pawel Kacprzak
DIFFICULTY:
Cakewalk
PREREQUISITES:
Adhoc, Strings
PROBLEM:
Given a string S of n uppercase Latin letters, your task is to decide if it is possible to rearrange letters in S in such a way that the resulting string will have a string LTIME as a prefix and a string EMITL as a suffix.
QUICK EXPLANATION:
It is sufficient to check if S contains enough letters to form the required strings as its prefix and its suffix.
EXPLANATION:
In both subtasks, you have to handle some number of test cases.
SUBTASK 1
You have to handle up to 100 test cases, but the good news is that each one contains a string S of length at most 9. In this case, we can try any possible arrangement of letters of S, in other words, every permutation of its letters, and for each one, check if it has the required strings as a prefix and as a suffix. The total time complexity of this method is O(T \cdot n! \cdot n) and it is enough, because n is at most 9 and we have at most 100 test cases to handle.
SUBTASK 2
The above method is only sufficient when dealing with such small inputs like we have in the first subtask. For the second subtask, it is way too slow, not only because we have up to 1000 test cases to handle, but mainly because n can be much larger here, up to 100. It is clear that we need a completely different approach here.
Let’s think for a second, do we need to consider any permutation of letters of S? Of course we don’t to do that. Notice that if there not enough letter to form both the required prefix and the required suffix, the answer is clearly NO. On the other hand, if there are enough letters in S to form the required prefix and the required suffix, the answer is YES.
First, we can notice that the shortest string containing required prefix and required suffix has length 9. This is true, because a string LTIMEMITL has length 9 and has the required prefix and suffix. Moreover, there is no such shorter string, because the longest prefix of EMITL which is also a suffix of LTIME has length 1.
Based on this observation, there are three cases to consider. If n = 9 then the answer is YES if and only if S contains two L, two T, two I, two M and one E. If n > 9, then the answer is YES if and only if S contains at least two L, at least two T, at least two I, at least two M and at least two E. If n < 9, then the answer is clearly NO.
The total complexity of this solution is O(n), because the only thing we have to do is to count occurrences of 5 different letters in S.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
