C# How to sort characters by insertion?

Question

C++ / C#

How to sort the numbers is understandable.
But what about symbols?
There are two lines :

string input = "AAAABBBCCDDDHH";
string willbe = "AABCHHDACBDDAB";

It is necessary to turn input into willbe, by sorting by inserts or by tree, and so that with a large length of lines, sorting is performed faster than 5 seconds.
Lines are always the same length and each character is repeated the same number of times in each line.
Please help.

Answer 1

1. Match each character in the second line with the number-index of that character;
   
2. For each character in the first line, look for the same character in the second line and match the current character with the index number of the second character;
   
3. We delete the found character from the second line - i.e. characters are repeated, you need to match the characters one to one;
   
4. Sort the first line by character numbers - if the number of identical characters in the lines matches, the result will correspond to the second line.