Anagrammes – Qualification 2006

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.