Finding all the ways the output needs to be scrubbed is disappointing. I don't mind doing this kind of problem, but if the requirements have to be reversed engineered by running attempts on a remote machine is beyond frustrating. Kind of wish there were tags or labels for "incomplete requirements". I don't mean to be too harsh, but spending time on something clunky like this makes need "to walk away".

Did you really mean to allocate a slice with '1<<62'?

Try this algorithm with two strings of 100, 1000, 10000, 100000, and see how well it does. I think Contains is likely O(n) and building the string will eat more memory than it needs to, but will be bound by the number of letters (26), so worst case 26*(27)/2, because of the string += creating intermediate strings.