Помогите оптимизировать код (время выполнения более 2 сек.) Python

Question

Задача:

Условия

Каждый пароль должен состоять из четного количества символов, и при этом первая половина пароля должна быть «анаграммно меньше» второй его половины. Теперь Василию нужен алгоритм, проверяющий, удовлетворяет ли придуманный пароль заданному условию. Вам дано n пар строк одинаковой длины (каждая строка – половина пароля).

Строка s считается анаграммно меньше строки t, если существуют строка s' и строка t' такие что:

    s' получается из s перестановкой букв
    t' получается из t перестановкой букв
    s' лексикографически меньше, чем t'

Для каждой пары строк si, ti определите правда ли, что si анаграммно меньше чем ti.

Формат входных данных

В первой строке задано целое число n - число пар строк в тесте (1 < n < 100).

В следующих 3n строках содержатся описания пар строк. Каждое описание состоит из трех последовательных строк. В первой строке каждого описания дана длина строк m_i (1 < m_i < 100), затем в следующих двух строках записаны строки s_i, t_i длины m_i, состоящие из строчных латинских букв.

Формат выходных данных

Для каждой пары строк из входных данных, выведите в i-й строке Yes, если строка s_i анаграммно меньше строки t_i. Иначе выведите No.

Собственно говоря код:

from collections import Counter
from itertools import permutations
#Получаем исходные данные
list_1 = []
n = int(input())
for i in range(n):
    list_1.append([int(input()), input(), input()])
#Удаляем лишние элементы
for item in list_1:
    item.pop(0)
#Определяем условия для нахождения анаграммы
#Строка s считается анаграммно меньше строки t,
#если существуют строка s' и строка t' такие что:
for item in list_1:
    #s' получается из s перестановкой букв
    #t' получается из t перестановкой букв
    s_1, s_2 = ''.join(sorted(item[0])), ''.join(sorted(item[1]))
    #s' лексикографически меньше, чем t'
    e, f = min(permutations(item[0])), max(permutations(item[1]))

    if Counter(s_1) == Counter(item[0]) and Counter(s_2) == Counter(item[1]) and e < f:
        print('Yes')
    else:
        print('No')

Код вроде работает, но при больших объемах данных выходит за рамки отведенного времени на выполнение.

Answer 1

Отсортируйте первую строку по возрастанию, а вторую по убыванию, и сравните результаты.

Answer 2

N = int(input())
results = []
for i in range(N):
    n = int(input())
    s = input()
    t = input()
    if str(sorted(s)) < str(sorted(t, reverse=True)):
        results.append("Yes")
    else:
        results.append("No")
for i in range(N):
    print(results[i])

БЛОГ НА HUSL

Помогите оптимизировать код (время выполнения более 2 сек.) Python

Ответы (2 шт):