Codeforces Round 937 (Div. 4) |
---|
Закончено |
Вам дана строка $$$s$$$ длиной $$$n$$$, состоящая из строчных латинских символов. Найдите длину самой короткой строки $$$k$$$, такой что несколько (возможно одна) копий $$$k$$$ могут быть сконкатенированы вместе, чтобы образовать строку той же длины, что и $$$s$$$, и при этом имеется не более одного отличающегося символа.
Формально, найдите длину самой короткой строки $$$k$$$, такой что $$$c = \underbrace{k + \cdots + k}_{x\rm\ \text{раз}}$$$ для некоторого положительного целого $$$x$$$, строки $$$s$$$ и $$$c$$$ имеют одинаковую длину и $$$c_i \neq s_i$$$ для не более чем одного $$$i$$$ (т.е. существует $$$0$$$ или $$$1$$$ такая позиция).
Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — количество тестов.
Первая строка каждого теста содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — длина строки $$$s$$$.
Вторая строка каждого теста содержит строку $$$s$$$, состоящую из строчных латинских символов.
Сумма $$$n$$$ по всем тестам не превышает $$$2\cdot10^5$$$.
Для каждого теста выведите длину самой короткой строки $$$k$$$, удовлетворяющей условиям в условии.
54abaa4abba13slavicgslavic8hshahaha20stormflamestornflame
1 4 13 2 10
В первом примере вы можете выбрать $$$k = \texttt{a}$$$ и $$$k+k+k+k = \texttt{aaaa}$$$, которая отличается от $$$s$$$ только во второй позиции.
Во втором примере вы не можете выбрать $$$k$$$ длиной один или два. Мы можем взять $$$k = \texttt{abba}$$$, которая равна $$$s$$$.
Название |
---|