Very nicely structured answer.
I was trying to realise something similar i.e. compare number with "sorted" one but fail on "number mooving backwad" and finally moved rough way.

Actually you do not need to sort all digits, you might need to find first number which is not in place.

Which is better than brute force O(n^2)

Not so easy. long long type have a limited size and hence n won't be too big. Also in "brute force" method you can make cheap iteration, especially by avoiding insert and erase string functions.

This solution doesn't actually understand the logic of the encoder. I was surprised by fact that other solutions actually understood logic of encoder.
This one is just based on fact that one letter transforms to one letter & same letter from same location transforms one way, not relying on other letters.
And then it just dynamically creates collection of encoded letters in all possible positions.

Performance: O(N) where N is length of the number.

So you want to say that 2 is same denominator as 12? Seriously?