Айбару подарили две строки a и b длины n, которая состоит из строчных латинских букв.
Айбар хочет сделать эти две строки одинаковыми. За один ход Айбар может выбрать любую длину l (1≤l≤n) и выполнить следующую операцию:
Он может выбрать одну подстроку строки a длины l и перевернуть ее;
Он в тот же момент должен выбирать подстроку строки b длины l и перевернуть ее.
То есть, за один ход Айбар может перевернуть одну подстроку из a и одну подстроку из b длины l.
Заметьте, что Айбар когда выбирает подстроку, их границы могут быть различны. Главное – Айбар должен выбирать подстроки одинаковых длин. Например, если l = 2 и n = 4, Айбар может перевернуть a[1…2] и b[2…3], a[3…4] и b[1…2], a[2…3] и b[2…3].
Скажите, может ли Айбар сделать строки a и b одинаковыми после какого то (либо 0) количества ходов.
Подстрока строки s — это последовательный отрезок букв из s. Например, defor – это подстрока codeforces, а fors — нет.
Входные данные
В первой строке входных данных дано одно целое число n (1≤n≤2⋅105) – длина строк.
Во второй строке входных данных дана строка a, состоящая из n строчных латинских букв.
В третьей строке входных данных дана строка b, состоящая из n строчных латинских букв.
Выходные данные
Выведите «YES» (без кавычек), если Айбар может сделать строки одинаковыми, или «NO» (без кавычек) иначе.
Ответы
Ответ:
Объяснение:
Айбар может сделать строки a и b одинаковыми только в том случае, если количество каждой буквы в строке a равно количеству этой же буквы в строке b. Это происходит потому, что каждая операция переворота подстроки меняет порядок букв в подстроке, но не меняет количество каждой буквы.
Таким образом, чтобы определить, может ли Айбар сделать строки одинаковыми, необходимо сравнить количество каждой буквы в строке a и строке b. Если для каждой буквы количество совпадает, то ответ будет "YES", в противном случае ответ будет "NO".
Пример решения на языке Python:
n = int(input())
a = input()
b = input()
count_a = [0] * 26 # массив для подсчета количества каждой буквы в строке a
count_b = [0] * 26 # массив для подсчета количества каждой буквы в строке b
for i in range(n):
count_a[ord(a[i]) - ord('a')] += 1 # увеличиваем счетчик для соответствующей буквы в строке a
count_b[ord(b[i]) - ord('a')] += 1 # увеличиваем счетчик для соответствующей буквы в строке b
if count_a == count_b:
print("YES")
else:
print("NO")
Данный код сначала создает два массива count_a и count_b размером 26, инициализированных нулями. Затем он проходит по каждой букве в строках a и b и увеличивает счетчики соответствующих букв в массивах count_a и count_b. После этого происходит сравнение массивов. Если они равны, то выводится "YES", иначе выводится "NO".