Yeah, I had a look at python solutions and if I ignore the solutions that trivialize the kata with builtins, incorrect solutions are common.

It's a beginner kata, it should catch beginner mistakes, and this task makes it easy to create a slightly wrong solution that naive random tests don't catch.

I suggest adding these 75 exhaustive size-4 fixed tests to all languages (gotta love how each language has its own code):

import itertools

def rename(xs):
    # my implementation is probably smooth-brained
    keys = itertools.count(1)
    known = {}
    out = []
    for x, i in sorted((x, i) for i, x in enumerate(xs)):
        if x not in known:
            known[x] = next(keys)
        out.append((known[x], i))
    return tuple(x for (x, i) in sorted(out, key=lambda xi: xi[1]))

size = 4
xs = list(map(list, set(itertools.chain(*map(itertools.permutations, set(map(rename, itertools.combinations_with_replacement(range(1, size+1), size))))))))
print(xs)
print(len(xs))

[[1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 2, 1], [1, 1, 2, 2],
 [1, 1, 2, 3], [1, 1, 3, 2], [1, 2, 1, 1], [1, 2, 1, 2],
 [1, 2, 1, 3], [1, 2, 2, 1], [1, 2, 2, 2], [1, 2, 2, 3],
 [1, 2, 3, 1], [1, 2, 3, 2], [1, 2, 3, 3], [1, 2, 3, 4],
 [1, 2, 4, 3], [1, 3, 1, 2], [1, 3, 2, 1], [1, 3, 2, 2],
 [1, 3, 2, 3], [1, 3, 2, 4], [1, 3, 3, 2], [1, 3, 4, 2],
 [1, 4, 2, 3], [1, 4, 3, 2], [2, 1, 1, 1], [2, 1, 1, 2],
 [2, 1, 1, 3], [2, 1, 2, 1], [2, 1, 2, 2], [2, 1, 2, 3],
 [2, 1, 3, 1], [2, 1, 3, 2], [2, 1, 3, 3], [2, 1, 3, 4],
 [2, 1, 4, 3], [2, 2, 1, 1], [2, 2, 1, 2], [2, 2, 1, 3],
 [2, 2, 2, 1], [2, 2, 3, 1], [2, 3, 1, 1], [2, 3, 1, 2],
 [2, 3, 1, 3], [2, 3, 1, 4], [2, 3, 2, 1], [2, 3, 3, 1],
 [2, 3, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1], [3, 1, 1, 2],
 [3, 1, 2, 1], [3, 1, 2, 2], [3, 1, 2, 3], [3, 1, 2, 4],
 [3, 1, 3, 2], [3, 1, 4, 2], [3, 2, 1, 1], [3, 2, 1, 2],
 [3, 2, 1, 3], [3, 2, 1, 4], [3, 2, 2, 1], [3, 2, 3, 1],
 [3, 2, 4, 1], [3, 3, 1, 2], [3, 3, 2, 1], [3, 4, 1, 2],
 [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3],
 [4, 2, 3, 1], [4, 3, 1, 2], [4, 3, 2, 1]]

(maybe they need to be renamed again so the answer isn't always either 2 or 3)

size-5 lists might have some limited value too, there are 541 of those though.

this is the code, can someone tell me if the test is broken of if it is just skill issue?

The test is not broken, what, I believe, leaves us only the latter option :)

Your solution fails one of example tests. Check which one, what is its input, and then try to figure out why.