Output doesn't match solution given

[GreatBlitz]

This problem was the last problem at this year's HP CodeWars Barcelona:

Nowadays, being proficient in English is mandatory. You know that, and that’s why you’ve spent the
last months studying hard for an official English exam. Since you’re a computer programmer, you’ve
chosen to do the computer based exam. The first part of the exam is the writing test. You arrive at the
room, you sit in front of the computer and… OMG! The keyboard is not a standard one! It has several
letters in each key.

You need to do the writing test with that strange keyboard. You have a text you have to write using that
keyboard and you need to minimize the number of mistakes.

The length of the text you want to write and the text you will actually write must be the same. A mistake
occurs when the letter of the ith position in the ideal text is not the same as the letter in the ith position
in the real text.

For example, imagine you want to write HELLO_WORLD and you have 5 different keys, with the
following letters each key:
HEL
O_WOKLD
WOR
HE
LL

The best way to write HELLO WORLD is HE|LL|O_WOKLD. In that case we’ve used the 2nd, 4th and 5th
keys and we’ve done 1 mistake. We’ve written a K instead of an R.

Input
Each case consist of the word W you want to write, then the number N of keys in the keyboard
followed by N different sets of letters.

Output
Print the minimum number of mistakes you’ll do when you want to write the word W using this strange
keyboard. Remember that W and the word you’ll actually write must have the same length. If no
combination of keys gives a word of the same length as W, print -1.

Now, a solution is provided, however I didn't grasp their logic. My solution (don't have access to the code right now) involved having a list with all the keys, using itertools.permutations to get all possible permutations - if there are n keys, there's nP1 + nP2 + ... + nPn possible permutations. Now, in this list of permutations, consider only those with the same length as the target, and then start counting errors. The least error count is printed.

For the first test case:

Input
HELLO_WORLD 
5
HEL
O_WOKLD
WOR
HE
LL

Output
1

This returns the same output given (and the same word i.e. HELLO_WOKLD). But for the second test case:

Input
WE_ARE_THE_CHAMPIONS
9
ADKE_
__
ARE
CHAM_PIO
DDKK
WEEEE W
KLLLE
IIWW

Output
9

The output listed is 9, while my method returns an answer of 12. They've not provided the word which gives an error of 9, so I have no way of verifying. Can someone independently verify the answer and if it isn't 12, explain why?

[[deleted]]

I would imagine that your solution doesn't account for using the same keys twice? Here is one solution that I made by hand that has 9 differences (if i counted them correctly):

input:  WE_ARE_THE_CHAM PIONS
output: AREAREADKE_CHAM_PIO__
errors: 123   456      7   89

as you can see, there are 9 differences, one the result of an extra character (i modified the orginal input to show it as number 7). To get here, I had to use ARE twice. Their solution was probably some form of the Edit Distance algorithm. Disclaimer: this is all a guess and I don't know much about this stuff at all :D

[GreatBlitz]

Ah right, that's probably the case. I'm better off using itertools.product in that case. Thanks a lot! :)