Counting number of swaps to make two strings equal in linear time

Question

The input to our problem is a pair of strings, say $x$ and $y$. We treat our alphabet size as a constant, i.e., our input is effectively a pair of arrays with the values therein bounded by a constant.

The problem is to compute the number of adjacent swaps (done to either of the strings), to make the strings equal. It is easy to see that our problem is equivalent to making $y$ equal to $x$.

One simple approach that I can think of is that we can first compute the appropriate permutation that makes $y$ into $x$ (easy to do in linear time) and then count number of inversions therein. Straightforward algorithms for inversion counting yield us $\mathcal{O}(n \lg n)$ overall running time. Chan and Pătraşcu show that this can be improved to $\mathcal{O}(n\sqrt{\lg n})$ if we use the fact that we deal with the special case of a permutation.

However, in the case of strings, we still have a bit more information than in the aforementioned case: our permutation comes from a pair of arrays with a constant number of possible values, whereas in the case of a permutation, the numbers can be $\mathcal{O}(n)$.

For example, in the case of a binary alphabet, I believe that the maximum number of swaps needed (inversions) is $\frac{n(n-1)}{4}$, so half the number possible in case of an arbitary permutation.

Moreover, in the case of equal number of zeros and ones (which I'm guessing would be the most complicated one), we have only ~ ${n\choose{n/2}} = \frac{n!}{\left(\frac{n}{2}!\right)^2}$ possible inputs to our algorithm, instead of $n!$. Correspondingly, we have $\lg\left(\frac{n!}{\left(\frac{n}{2}!\right)^2}\right) = \Theta(n)$, in contrast to $\lg(n!) = \Theta(n\lg n)$. Therefore, simple counting lower bounds similar to that question would also not seem to apply.

Are better algorithms known for this special case?

Answer 1

The answer is yes, as a linear-time algorithm is possible if the alphabet size is constant. I explain a $\Theta(k n)$-time algorithm here, where $k$ is the size of the alphabet.

It is easier to see the problem if the permutation is represented as a bipartite graph on the plane, like this image (ignore the upper graph). The edge set is $E = \{(i,p_i)\}_i$. The inversions are same as intersections between two edges: $\{ (i,p_i), (j, p_j) \in E \mid i < j \land p_i > p_j \}$.

First, notice that if the edge set is partitioned into $k$ sets for each alphabet, then each edge subset is monotone. That is, two edges can only intersect between different alphabets. Let $E^a$ to denote the edge subset of alphabet $a$.

We can count the number of intersections between two edge subsets $E^a, E^b$ in a linear time. The algorithm iterates the edges in a subset $E^a$. The edges in $E^b$ intersecting to an edge in $E^a$ can be represented as a (possibly empty) interval. Furthermore, the endpoints of the intervals can only go up during the iteration. Thus, by maintaining the endpoints of the intersecting interval, this subproblem can be solved in $\Theta(|E^a| + |E^b|)$ time.

Pseudocode is as follows:

def count_intersections(as, bs):
  # Loop invariant: (l, r) are endpoints of the intersecting interval such that
  # (l <= j < r) if and only if as[i] and bs[j] intersect.
  l, r = 0, 0
  total = 0
  for i in 0..len(as):
    while r < len(bs) && bs[r].1 < as[i].1:
      r += 1
    while l < r && !(as[i].0 < bs[l].0):
      l += 1
    total += r - l
  return total

The answer is the sum of all answers of such subproblems for each pair of edge sets. Because each edge occurs in at most $k$ subproblems, and the edge sets can be constructed in $O(n + k)$ time, the running time of the algorithm is $O(k n)$.