11092. Minimum string

Phineas and Ferb really want to appear in the credits stored on Candace’s computer. They know that Candace is afraid of forgetting the password, so she keeps a hint: two strings a and b, consisting of lowercase English letters.

This morning, Ferb learned the rule by which the password can be derived from the hint.

Consider the following operation:

· Choose any position in string a. Choose any position in string b.

· Swap the characters at these positions.

The password is the lexicographically smallest string a that can be obtained by applying any number of such operations. Help the guys compute the password.

Input. The first line contains string a, and the second line contains string b (1 ≤ |a|, |b| ≤ 10⁵). Both strings consist of lowercase English letters.

Output. Print the computed password.

Sample input	Sample output
hello myworld	dehll

SOLUTION

strings

Algorithm analysis

The lexicographically smallest letters can always be inserted into string a (at any position) using the described operation.

Let’s combine strings a and b. Let s = a + b. Sort the letters of string s in ascending order. The lexicographically smallest letters will be at the beginning of string s. If string a contains k letters, the password will be the prefix of string s of length k.

Algorithm implementation

Read the input strings a and b.

cin >> a;

cin >> b;

Combine strings a and b and sort the resulting string.

s = a + b;

sort(s.begin(), s.end());

Print the answer – the prefix of string s with a length equal to a.size().

cout << s.substr(0, a.size());

Python implementation

Read the input strings a and b.

a = input()

b = input()

Combine strings a and b.

s = a + b

Sort the string s.

s = ''.join(sorted(s))

Print the answer – the prefix of string s with a length equal to len(a).

print(s[:len(a)])