Since the requirements became stronger, and time was reduced from 2 sec down to 1 sec, now it is not possible to resolve the task using bruteforce method, python is very slow for such hard requirements.

Even I do empty loops the taken time is already about 1.3 sec.

from time import time
time_before = time()

len_lst = 20

for i in range(1, ((2 ** len_lst) // 2) - 1):

    for j in range(len_lst):

        pass

print(time() - time_before)

>>> 1.3192360401153564

I think for Python the time should be rolled back to 2 sec.
Of cause if I use bruteforce on "C" it takes about 0.2 sec, but Python is not "C".

Finally I could resolve the task on Python using DP for 0.65 sec.