Minimum cost to convert string S to good string

Question

Given a string $S$ of $0$ and $1$ we need to convert it into a good string. A string is called good if and only if :

Their are no two or more $0s$ or $1s$ together. It means $001$ is not good but $010$ is a good string.

Now we can swap positions of any two indexes of $S$. Let the cost of swapping from position $i$ with position $j$ $(i ≠ j)$ be $C(i, j)$.

Now we have two types of costs calculation :

1. $C(i,j)=|j-i|$
2. $C(i,j)=|j-i|^2$

We need to find minimum cost of swaps needed to convert the current string $S$ into a good string.

Also if its not possible to convert string $S$ into good string then also we need to tell that like if S=$00$ then we can never convert it into good string.

Example : Let string $S=0011$ then if cost is of type $1$ that is we can swap any two positions and cost will $|j-i|$ then answer is $1$ and also for type 2 cost as $(3-2)^2=1$

Answer 1

First, suppose a string has $a$ zeros and $b$ ones. Then you can permute it into a good string iff $|a-b|\le1$. If $a=b+1$ the only possible good string is $01010\cdots010$, and if $b=a+1$ it is $10101\cdots101$. If $a=b$ there are two good strings ($0101\cdots01$ and $1010\cdots10$), so if you have a general algorithm for finding the minimal number of swaps, you can simply compute the number of swaps to each of the two good strings separately, and choose whichever one gives you the smaller number of swaps.

For any nonnegative $a$ and $b$, we let $S(a,b)$ denote the set of strings with $a$ zeros and $b$ ones. Any two strings $s$ and $t$ in $S(a,b)$ can be connected by a sequence of swaps. We give a simple greedy algorithm to find a minimal-cost sequence of swaps, where the cost of a single swap is a nonnegative number $C(i,j)\ge0$; our algorithm assumes that

$(*)$ $C(i,j)+C(j,k)\le C(i,k)$ iff $i\le j\le k$

Both of the cost functions in the question satisfy this condition. In essence, this says you want to swap adjacent elements whenever possible, and we'll see that there is an optimal solution which only swaps adjacent elements. Cost functions such as $\sqrt{|i-j|}$ or $|i-j|+1$ are more interesting; we don't solve such cases here.

It's convenient to let $d(s,t)$ denote the cost of a minimal-cost sequence of swaps taking $s$ to $t$; we essentially just need to compute $d$. It is convenient to set $C'(i,j)=C(i,i+1)+\cdots+C(j-1,j)$; by $(*)$ we have $C'(i,j)\le C(i,j)$. For both of the cost functions given in the problem, it's easy to see that $C'(i,j)=|i-j|$; this is the minimum possible cost of a sequence of swaps moving element $i$ to element $j$.

Let $i_1\le i_2\le\cdots\le i_a$ and $j_1\le j_2\le\cdots\le j_a$ be the locations of the zeros in $s$ and $t$ respectively. By the above remarks, a lower bound for $d(s,t)$ is given by $$\min_{\pi\in S_a}\sum_{r=1}^a C'(i_r,\pi(j_r))$$ where the minimum is over all permutations $\pi$ of the $j_r$'s. It's not hard to see that the minimum sum is achieved at the identity permutation, so $d(s,t)$ is bounded below by the sum $$ B(s,t) :=\sum_{r=1}^a C'(i_r,j_r).$$ If we can find a sequence of adjacent swaps such that the zero at $i_r$ moves to position $j_r$ for each $r=1,\ldots,a$, and such that each individual swap moves exactly one zero closer to its target, then we conclude $d(s,t)=B(s,t)$, as the cost of that sequence of swaps is precisely $B(s,t)$. (The trick is to avoid "bumping into" other zeros on the way.) In particular, for both of the cost functions in the problem, we will show that $$ d(s,t) = \sum_{r=1}^a |i_r-j_r|.$$

We show that, as long as $i_r\ne j_r$ for at least one $r$, there's at least one swap which moves exactly one zero one step closer to its target. Label each $i_r$ with $\mathrm{sign}(j_r-i_r)$; that is, $i_r$ is $+$ if $i_r$ needs to move right, $-$ if it needs to move left, and $0$ if it's already in the right place. The key observation is:

A zero can be swapped one position to the right if it is at the rightmost end of a string of $+$'s, or to the left if it is at the leftmost end of a string of $-$'s.

(To see this, look at the first case. We have $i_r<j_r$ and either $r=a$ or $i_{r+1}\ge j_{r+1}$, so the zero won't "bump into" any other zeros on the way from $i_r$ to $j_r$.) After swapping $s_{i_r}$ with its right neighbor if the label is $+$ (or its left neighbor if the label is $-$) to obtain a new string $s'$, we have $B(s',t) = B(s,t)-1$ and we apply the same procedure to $s'$.

An example is probably useful here. Let $s=0101110$, so the "good" target is $t=1010101$. We have $B(s,t)=C'(1,2)+C'(3,4)+C'(7,6)=3$, so our algorithm should produce a sequence of $3$ adjacent swaps. The labels for the $0$'s in $s$ are $++-$, so we can safely move the second $0$ right (the swap $(3,4)$) or the third zero left (the swap $(7,6)$). Say we take the first choice; we get $s'=0110110$, labels $+0-$, so we can now either move the first zero right, or the last zero left. Either way, the algorithm returns a unique third swap.