Just one suggestion.
I found this kata particularly hard and not because the exercise it's hard by itself.
I found it hard because I think instructions could be somewhat improved:

1.- Explain invalid characters.
I know there is awesome people that can see this rule even if it is not present in the visible test cases/examples. But mortals like me needed to change their design several times because each time a new rule appeared.

2.- Explain that several spaces or underscores must be replaced by single spaces.
Again, I'm just a mortal, and took me a long time to be guessing some rules that weren't explained.

Despite of this it's a good kata, thanks for this kind of exercises.
Regards!.

Sorting was Hard, took my time to figure out what type of sorting was required.
Also achieved to solve it for "N" strings instead of 2 only.

This will work for "N" strings, not just for 2.

Seems like C++ tests are broken. Had to make it in C#.

C++ random test segfaults, but maybe you can submit your answer as C. Solution should be similar and C test doesn't segfaults.