Conjecture about reversal operations on strings (with duplicates) Note: If you can find a proof of this, please give me just a hint first, so I can try to solve it on my own.
Let $\Sigma$ be a finite alphabet (set of symbols) and $s,t\in\Sigma^\ast$ two strings (sequences of symbols) of equal length $n$ over $\Sigma$. We denote by $s_i\in \Sigma$ the $i$-th symbol of $s$, and by $as\in\Sigma^{n+1}$ the concatenation of the symbol $a\in\Sigma$ with $s\in\Sigma^n$. First, define a reversal operation $\text{r}(i,j)$ on $s$ as the operation:
$$s=s_1...s_n\quad\mapsto\quad s_1...s_{i-1}\ \ s_j s_{j-1}...s_{i+1}s_i\ \ s_{j+1}...s_n$$
that extracts the substring $s_i\dots s_j$ from $s$, reverses it, and puts it back in the same place, where $1 \le i\le j \le n$. Then, define the reversal distance $d_r(s,t)$ between $s$ and $t$ as the minimum number of reversal operations (on either $s$ or $t$) needed to transform $s$ into $t$ ($d_r(s,t):=\infty$ if not possible).
Conjecture: Let $a\in\Sigma$ and $s,t\in\Sigma^n$. Prove (or find a counterexample) that:
$$d_r(as,at)=d_r(s,t)$$
(In other terms, we can disregard the longest common prefix between two given strings when transforming one into the other.) Note that $a$ can occur in $s,t$.

Example: $a=1,\ s=23141,\ t=41123$
$$
\begin{array}{cl|cl}
as\to^2 at           &                & s\to^2 t          &                \\ \hline
\underline{1\ 23}141 & \text{r}(1,3)\ & \underline{2314}1 & \text{r}(1,4)\ \\ 
\underline{3\ 21141} & \text{r}(1,6)\ & 41\underline{321} & \text{r}(3,5)\ \\ 
           1\ 41123  &                & 41123             &                \\ \hline
\end{array}
$$

A few remarks:


*

*That $d_r(as,at)\le d_r(s,t)$ is obvious, the converse less so.

*If $n\gt 0$ and $d_r(as,at)=1$ then $d_r(s,t)=1$.

*If $n\gt 0$ and $a$ does not occur in $s,t$, then it must return at the initial position at some point. Therefore, the same reversal operations that transform $as$ into $at$ can be easily adjusted to transform $s$ into $t$, so that the relative positions between all the other symbols excluding $a$ remain the same. This implies the conjecture in this case.

*Induction alone doesn't seem to be powerful enough. Also, most results I've found in the literature either provide lower/upper bounds on the minimum $k$, or concern the computational complexity of this kind of problems, collectively known as sorting by reversals.

*I tested it via computer on random instances up to a reasonably high $n$ and it seems to hold.



I've edited this question numerous times, mainly to consider some variation of the conjecture. We write $s\to^k t$ if $s$ can be transformed into $t$ by application of exactly $k$ reversals:


*

*Assume $i\lt j$ (i.e. $\text{r}(i,i)$ are disallowed). Prove that if $as\to^k at$ then $s\to^k t$. Counterexample:
$$
\begin{array}{cl|cl}
as\to^1 at               &                & s\to^1 t  &     \\ \hline
\underline{1\ 1}23123... & \text{r}(1,2)\ & 123123... & ? \ \\ 
           1\ 123123...  &                & 123123... &     \\ \hline
\end{array}
$$

*Assume $i\lt j$ (i.e. $\text{r}(i,i)$ are disallowed). Prove that if $as\to^k at$ and $s\neq t$ then $s\to^k t$. Counterexample:
$$
\begin{array}{cl|cl}
as\to^3 at         &                & s\to^3 t &     \\ \hline
\underline{1\ 23}4 & \text{r}(1,3)\ & 234      & ? \ \\ 
3\ 2\underline{14} & \text{r}(3,4)\ &          & ? \ \\ 
\underline{3\ 241} & \text{r}(1,4)\ &          & ? \ \\ 
           1\ 423  &                & 423      &     \\ \hline
\end{array}
$$

*For sake of completeness, the original conjecture above can be practically re-written as: Prove that if $n\gt 0$ and $as\to^k at$ then $s\to^k t$.

Edit: Possible counterexample to the original conjecture:
$$
\begin{array}{cl|cl}
as\to^3 at              &                & s\to^3 t &     \\ \hline
\underline{4\ 221}31441 & \text{r}(1,4)\ & 22131441 & ? \ \\ 
1\ 2\underline{2431441} & \text{r}(3,9)\ &          & ? \ \\ 
\underline{1\ 2144}1342 & \text{r}(1,5)\ &          & ? \ \\ 
           4\ 41211342  &                & 41211342 &     \\ \hline
\end{array}
$$
 A: Here is a check in Python that your proposed counterexample is indeed a counterexample. I took the subflip function from @AleksejsFomins's answer.
import itertools

def subflip(s, i, j):
    return s[:i] + s[i:j][::-1] + s[j:]

s = "22131441"
t = "41211342"

flipped_strings = set([s])
num_flips = 0

while True:
    if t in flipped_strings:
        print("Minimal number of flips:", num_flips)
        break

    new_flipped_strings = set()
    for i, j in itertools.combinations(range(len(s) + 1), 2):
        new_flipped_strings.update(subflip(f, i, j) for f in flipped_strings)

    flipped_strings = new_flipped_strings
    num_flips += 1

The output is (near instantaneously):
Minimal number of flips: 4

And indeed, if you prepend the 4 on both strings this script confirms that three flips suffice to change one string into the other.
A: I have run a numerical simulation on your proposed counter-example, and the minimal number of flips for the string without prefix is 4, which is more than 3
CODE (Python3)
def subflip(s, i, j):
    return s[:i] + s[i:j][::-1] + s[j:]

s1 = "22131441"
s2 = "41211342"
N = len(s1)

def test(s1, s2, pref, depth):
    for i in range(N-1):
        for j in range(i+2, N+1):
            s1_a = subflip(s1, i, j)
            pref_a = pref+[(i, j)]
            if s1_a == s2:
                print(s1_a, s2)
                print("Win", pref_a)
                return True

            if depth - 1 > 0:
                if test(s1_a, s2, pref_a, depth-1):
                    return True
    return False

test(s1, s2, [], 4)

Answer:
Win [(0, 4), (0, 6), (3, 8), (4, 7)]

Edit: This is a depth-first search, so I ran the code several times for increasing value of depth until I got an answer
Note: I do not believe I deserve the bounty, because you proposed the counter-example yourself, I just checked it
