title: Counting the adjacent swaps required to convert one permutation into another
body: <blockquote>
    <p>We're given two sequences of lowercase latin alphabet letters.
    They're both the same length and have the same amount of given types
    of letters (the first has an equal number of t's as the second and so
    on). We are required to find the minimum number of swaps (<em>by "swap" we mean changing
    the order of two <strong>neighboring</strong></em> letters) required to
    transform the first sequence into the second. We 
    can safely assume every two sequences CAN be transformed
    into each other. We could do this with brute-force, but the sequences are too long for that.</p>
    
    <p><strong>Input:</strong><br>
    The length of the sequences (at least 2, at most 999999) and
    then two sequences.</p>
    
    <p><strong>Output:</strong><br>
    An integer representing the number of swaps needed for the
    sequences to become the same.</p>
    
    <p><strong>Example:</strong><br>
    {5, aaaaa, aaaaa} should output {0},<br>
    {4, abcd, acdb} should output {2}.</p>
  </blockquote>
  
  <p>The first thing that came to my mind was bubblesort. We can simply bubblesort the sequence counting each swap. The problem is: a) it's O(n^2) worst-case b) I'm not convinced it would give me the smallest number for every case... Even the optimized bubblesort doesn't seem to be doing the trick. We could implement the cocktail sort which would solve the problem with turtles - but will it give me the best performance? Or maybe there's something simpler/faster?</p>
  
  <p>This question can also be phrased as: <strong>How can we determine the edit distance between two strings when the only operation allowed is transposition?</strong></p>