Here's my obligatory silly answer:

f[s_, t_, e_] := With[{r = #[[1]] -> #[[2]] & /@ e},
  StringReplace[s, r] != StringReverse[StringReplace[t, r]]]
p[{s_, t_}] := StringMatchQ[s, t ~~ __] || StringMatchQ[t, s ~~ __]
p[e_] := Or @@ p /@ Subsets[#[[2]] & /@ e, {2}]
m[s_, t_, k_] := Module[{h = Union @@ Characters /@ {s, t}, e, b = True},
  While[b, e = h /. c_String :> {c, 
   StringJoin[ToString /@ RandomInteger[k - 1, RandomInteger[{1, 10^6}]]]};
   b = p[e] && f[s, t, e]]; e]

Example usage:

m["We wish you the best", "Sz is the handsomest groom", 3]

It will return a list representing the encoding, such as:

{{"W", "012"}, {"e", "2111"}, ...}

It'll probably work, but I wouldn't try to run it.

I'm not particularly good at golf, but if you take my handicap into consideration, I'm sure I stand a good chance. ;-)

Here's my obligatory silly answer:

f[s_, t_, e_] := With[{r = #[[1]] -> #[[2]] & /@ e},
  StringReplace[s, r] != StringReverse[StringReplace[t, r]]]
p[{s_, t_}] := StringMatchQ[s, t ~~ ___] || StringMatchQ[t, s ~~ ___]
p[e_] := Or @@ p /@ Subsets[#[[2]] & /@ e, {2}]
m[s_, t_, k_] := Module[{h = Union @@ Characters /@ {s, t}, e, b = True},
  While[b, e = h /. c_String :> {c, 
   StringJoin[ToString /@ RandomInteger[k - 1, RandomInteger[{1, 10^6}]]]};
   b = p[e] || f[s, t, e]]; e]

Example usage:

m["We wish you the best", "Sz is the handsomest groom", 3]

It will return a list representing the encoding, such as:

{{"W", "012"}, {"e", "2111"}, ...}

Description: Creates a random encoding e of all the characters while it is prefixed p[e] or doesn't encode the strings to be the reverse of each other f[s, t, e].

It'll probably work, but I wouldn't try to run it.

I'm not particularly good at golf, but if you take my handicap into consideration, I'm sure I stand a good chance. ;-)