Anagrammes – Qualification 2006

Level 4

ENONCE

On donne en argument un mot s1 et un de ses anagrammes s2. écrire une fonction qui renvoie le nombre minimal de permutations à effectuer pour obtenir s2 en partant de s1. Une permutation est l'échange de deux caractères consécutifs.

Exemple avec chien et niche :

chien -> chine -> chnie -> cnhie -> nchie -> ncihe -> niche

La fonction renvoie donc 6.

CONTRAINTES

  • s1 et s2 ont la même longueur N
  • N \<= 10000

ENTREE

  • La première ligne de l'entrée contient un entier : N.
  • La deuxième ligne contient la chaîne de caractères s1.
  • La troisième ligne contient la chaîne de caractères s2

SORTIE

La sortie contient une unique ligne : l'entier retourné par votre fonction.

Runtime constraints

Maximum memory usage
5000 kilobytes
Maximum execution time
1500 milliseconds

Input/output samples

Sample input
5
chien
niche
Sample output
6

Submit your solution

You have to register or log in to be able to submit your solution.