title: Fastest way to sort string to match second string - only adjacent swaps allowed
body: <p>I want to get the minimum number of letter-swaps needed to convert one string to match a second string. Only adjacent swaps are allowed.</p>
  
  <p>Inputs are: length of strings, string_1, string_2</p>
  
  <p>Some examples:</p>
  
  <pre class="lang-none prettyprint-override"><code>Length | String 1 | String 2 | Output
  -------+----------+----------+-------
     3   | ABC      | BCA      |   2 
     7   | AABCDDD  | DDDBCAA  |  16
     7   | ZZZAAAA  | ZAAZAAZ  |   6
  </code></pre>
  
  <p>Here's my code:</p>
  
  <pre><code>def letters(number, word_1, word_2):
  
      result = 0
  
      while word_1 != word_2:
          index_of_letter = word_1.find(word_2[0])
          result += index_of_letter
          word_1 = word_1.replace(word_2[0], '', 1)
          word_2 = word_2[1:]
  
      return result
  </code></pre>
  
  <p>It gives the correct results, but the calculation should stay under 20 seconds.</p>
  
  <p>Here are two sets of input data (1 000 000 characters long strings):  <a href="https://ufile.io/8hp46" rel="nofollow noreferrer">https://ufile.io/8hp46</a> and <a href="https://ufile.io/athxu" rel="nofollow noreferrer">https://ufile.io/athxu</a>.</p>
  
  <p>On my setup the first one is executed in around 40 seconds and the second in 4 minutes.</p>
  
  <p>How to calculate the result in less than 20 seconds?</p>