 # ALLSUM - Editorial (Unofficial)

Editorialist: Darshan Sen

EASY

Greedy

# 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;
int R_frequency;

// 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) in R?
Well, going by the definition of the
lexicographical order, we find the first
character in S that differs from S.
If it is lesser that S, 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 */
char temp_ch = S;
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
to res in a sorted order. */
for (char ch = 'a'; ch < S; ++ch) {
int id = int(ch - 'a');
while (R_frequency[id]--)
res = res + ch;
}

if (temp_ch < S) {
// S chould come before the cluster of S's

// we first append S to the result
res += S;

// then we append the cluster of S's
int temp_id = int(S - 'a');
while (R_frequency[temp_id]--)
res = res + S;
} else {
// the cluster of S's should come before S

// we first append the cluster of S's
int temp_id = int(S - 'a');
while (R_frequency[temp_id]--)
res = res + S;

// then we append S to the result
res += S;
}

/* We append all the remaining
characters < S to res again
in a sorted order. */
for (char ch = char(1 + S); 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;
}

1 Like