Needle in a Haystack

We need rearrange all letters of t, and somewhere inside that rearranged string, s must appear as a subsequence.

The key phrase is subsequence, not substring. The letters of s do not need to be adjacent, but they must appear in order.

A tempting wrong move is to just sort t. Sorting gives the smallest possible string with no restrictions, but it might destroy the required order of s. Cheap string, invalid answer. Sad trombone.

So the real problem is:

Build the lexicographically smallest permutation of the multiset of letters in t, while guaranteeing that a left-to-right scan can match all of s.

If t does not even contain the required letters of s, print Impossible. That part is non-negotiable.

The Greedy View

Suppose we are building the answer from left to right.

Let pos be how much of s we have already matched. So s[0..pos-1] is already matched, and we still need to match the suffix s[pos..].

At some step, we want to place the smallest possible next character. A character ch is valid if, after using it, it is still possible to complete the remaining suffix of s from the letters we have left.

That is exactly the kind of check greedy needs.

For example, if pos = 3, then the future still needs all letters from s[3..], with multiplicity. If the remaining multiset does not cover those needed counts, we are cooked.

Why Matching Immediately Is Correct

If the next chosen character equals s[pos], we advance pos.

Could it ever be better to treat that character as “extra” and not match it?

No. Matching it immediately consumes the same character either way, but reduces the future required suffix. That cannot make the situation worse. Delaying the match is just doing mental gymnastics to end up with fewer options.

So the state transition is simple:

• choose some available letter ch
• remove it from the remaining count
• if pos < |s| and ch == s[pos], increment pos
• check whether the remaining letters can still cover s[pos..]

Fast Feasibility Checks

There are only 26 lowercase letters, so we can store counts in arrays of size 26.

Precompute:

$$need[i][c] = \text{number of occurrences of character } c \text{ in } s[i..|s|-1]$$

Then, after a possible move to state pos, the remaining letters are feasible iff:

$$remaining[c] \ge need[pos][c]$$

for every character c.

Since there are only 26 letters, checking this is cheap.

Greedy Algorithm

For each output position:

1. Try ch = 'a' to 'z'.
2. If ch is unavailable, skip it.
3. Temporarily use it.
4. Compute the new matched position.
5. Check if the remaining counts can still form s[newPos..] as a subsequence.
6. The first valid ch is forced into the answer.

Because lexicographic order is decided at the first differing position, picking the smallest valid next character is always optimal. Any smaller invalid character would make it impossible to finish, so it is fake cheapness.

Correctness Proof

First, the impossibility check is correct. If some letter appears more times in s than in t, then no permutation of t can contain s as a subsequence, because every matched character must come from t. Conversely, if all counts are sufficient, at least one valid arrangement exists: place s itself, then place all leftover letters anywhere.

Now consider one step of the greedy construction. Assume the already-built prefix is fixed and validly extendable, and pos is the length of the prefix of s already matched by this prefix.

The algorithm tries letters in increasing order and chooses the first one that leaves enough remaining letters to match s[pos..] after the transition. Therefore, after choosing this letter, at least one valid completion exists.

Every smaller letter was tested and rejected. Rejection means that after placing it, the remaining multiset cannot cover the still-unmatched suffix of s, so no valid full answer can start with the current prefix plus that smaller letter.

Thus the chosen letter is the smallest possible next character among all valid completions. Repeating this at every position gives the lexicographically smallest valid string.

Finally, whenever the chosen letter equals the next needed character of s, advancing pos is safe because it only decreases the future subsequence requirement.

Therefore, the algorithm is correct.

Complexity

For each output character, we try at most 26 letters, and each feasibility check scans 26 counts.

So the complexity is:

$$O(26^2 \cdot |t|)$$

which is easily fine for $\sum |t| \le 10^5$. Memory is $O(26 \cdot |s|)$ for suffix counts.