PROBLEM LINK:
Practice
Contest[Division 1]
Contest[Division 2]
Author: Mohammad Shahhoud
Editorialist: Darshan Sen
DIFFICULTY:
EASY
PREREQUISITES:
PROBLEM:
Given 2 strings S and R, find the lexicographically smallest permutation of R s.t.:
all substrings of S \subseteq all substrings of R
QUICK EXPLANATION:
Remove the characters of S from R, sort the remaining characters of R and finally inject S into the formed string in its appropriate position.
SOLUTIONS:
A necessary and sufficient condition for the required permutation of R to exist is when it contains S as a substring in it. The reason is that, all the substrings of S are already included in S. We break down our work into a few cases.
Case 1
|R| < |S|
Here the solution doesn’t exist as, to have all substrings of S in all substrings of R, R must be atleast of the size of S. Hence, the required permutation is "Impossible".
Case 2
|R| \geq |S|
We store the frequency of each character in S and R in 2 containers, S_{frequency} and R_{frequency} respectively. Since we know that S must appear as a substring in the solution permutation of R, we first remove the characters of S_{frequency} from R_{frequency}.
Case 2.1
If we get a negative result when we subtract the frequency of a character present in S from R_{frequency}, it means that R does not possess the sufficient quantity of the character, which is contained in S. Hence, the required permutation is "Impossible".
Case 2.2
Now that we have successfully removed the characters of S from R_{frequency}, we generate a string by forming a sequence of ordered clusters of the characters denoted by R_{frequency} and inject S in the correct position.
We do this by first finding the first character in S that differs from S_0. If it is lesser than S_0, we inject S in the beginning of the S_0 cluster or else, we append it to the S_0 cluster.
Time Complexity
O(max(|R|, |\sum|))
Editorialist's Solution
#include <iostream>
std::string S, R;
std::string solve (void ) {
// store sizes
int S_size = S.size();
int R_size = R.size();
if (R_size < S_size) {
/* because to have S as a substring in R,
R must be larger than or the same size as S*/
return "Impossible";
} else {
/* frequency to store the count
of characters in S and R */
int S_frequency[26];
int R_frequency[26];
// filling with 0 initially
std::fill(S_frequency, S_frequency + 26, 0);
std::fill(R_frequency, R_frequency + 26, 0);
// filling in the frequencies
for (int i = 0; i < S_size; ++i)
++S_frequency[int(S[i] - 'a')];
for (int i = 0; i < R_size; ++i)
++R_frequency[int(R[i] - 'a')];
/* To have all the substrings of S
in the set of all substrings of R,
it would be sufficient to have just
S as a substring in R. */
/* To find the lexicographically
minimum of such permutations of R,
we simply keep all the remaining
characters of R sorted and inject
string S into its appropriate position. */
/* There is however one more thing we
should be worried about. Where exactly do
we inject S if there exists a cluster of
characters( = S[0]) in R?
Well, going by the definition of the
lexicographical order, we find the first
character in S that differs from S[0].
If it is lesser that S[0], we place S
in the beginning of the cluster.
In the other case, we put it at the end.*/
// removing the obvious characters of S from R
for (int i = 0; i < 26; ++i) {
R_frequency[i] -= S_frequency[i];
if (R_frequency[i] < 0) {
/* R doesn't have as many
number of character
char('a' + i) as S. */
return "Impossible";
}
}
/* temp_ch stores the first character
in S that differs from S[0] */
char temp_ch = S[0];
for (int i = 0; i < S_size; ++i) {
char ch = S[i];
if (ch != temp_ch) {
temp_ch = ch;
break;
}
}
/* res stores the result and is
initialized with the empty string*/
std::string res;
/* We append all the characters < S[0]
to res in a sorted order. */
for (char ch = 'a'; ch < S[0]; ++ch) {
int id = int(ch - 'a');
while (R_frequency[id]--)
res = res + ch;
}
if (temp_ch < S[0]) {
// S chould come before the cluster of S[0]'s
// we first append S to the result
res += S;
// then we append the cluster of S[0]'s
int temp_id = int(S[0] - 'a');
while (R_frequency[temp_id]--)
res = res + S[0];
} else {
// the cluster of S[0]'s should come before S
// we first append the cluster of S[0]'s
int temp_id = int(S[0] - 'a');
while (R_frequency[temp_id]--)
res = res + S[0];
// then we append S to the result
res += S;
}
/* We append all the remaining
characters < S[0] to res again
in a sorted order. */
for (char ch = char(1 + S[0]); ch <= 'z'; ++ch) {
int id = int(ch - 'a');
while (R_frequency[id]--)
res = res + ch;
}
return res;
}
}
int main (void ) {
int N;
std::cin >> N;
while (N--) {
std::cin >> S >> R;
std::cout << solve() << std::endl;
}
return 0;
}