We all know a conspicuous member of our community got hitched recently. As most of us are not in Malta, and weren't able to fly there, I thought of a celebration question. Sort of.

The challenge is golfing a function (Mma only) that finds a prefix free encoding for the letters of two sentences.

The trick is that both sentences (given as parameters) must share the same encoding, with one of them written backwards.

The number of available symbols for the encoding is also a parameter for the function (always less than 10), and the function should attempt to find the shortest encoding for that number of symbols. There is no a-priori guarantee that a solution exists for every parameter set.

As an example, related to our celebration:

we wish you the best

and

sz is the handsomest groom

Inspiration was taken from this question (which does not require a prefix free code), but is a good explanation of what is required.

Happy wedding and golfing!

Shortest code wins!

PS: A bounty of 100, a wedding garter and the party leftovers to the winner

EDIT Clarifications. To be updated as comments and answers arise

1. No caps. Only lowercase.
2. No need to encode whitespaces, special chars or punctuation (skip them and consider only lowercase letters)
3. Your solution should be able to show up results before they are back from the honeymoon.