We consider two integers to be similar if, when written in decimal, have the same length, and if we compare characters in any two positions for both decimal strings, the comparison results (less, equal or greater) must be the same in both strings.
Formally, for two number that can be written as decimal strings \$a_1a_2\cdots a_n\$, \$b_1b_2\cdots b_m\$, they're similar if and only if \$n=m\$ and \$a_i<a_j\ \leftrightarrow b_i<b_j\$ (\$\leftrightarrow\$ means if and only if) for all \$ i,j \in [1,n]\$.
For example, 2131 and 8090 are similar. 1234 and 1111, 1234 and 4321 are not similar.
For a given positive integer, find a different non-negative integer similar to it. You can assume at least one such integer exists.
Your implementation shouldn't be too inefficient. It must be at least able to pass the samples in around one hour on an average computer. (If it doesn't end in a few seconds, consider providing a screenshot running it)
Your code can take the input and output as integers, strings or lists of digits. Standard loopholes are forbidden.
Since this is a code-golf, the shortest code in bytes wins!
It's (quite) possible to have different outputs on these inputs as long as inputs and outputs are different and similar.
1 - 0 3 - 9 9 - 1 19 - 23 191 - 121 1111 - 2222 (0 is not considered valid) 2020 - 9393 2842 - 1321 97892 - 31230 113582 - 113452 444615491 - 666807690 87654321000 - 98765432111 98765432111 - 87654321000 526704219279 - 536714329379 99887766553210 - 88776655443210
Sample inputs as a list: