Nearly Shortest Repeating Substring (Codeforces 1950E)
Tags: Implement, strings

You are given a string $$$s$$$ of length $$$n$$$ consisting of lowercase Latin characters. Find the length of the shortest string $$$k$$$ such that several (possibly one) copies of $$$k$$$ can be concatenated together to form a string with the same length as $$$s$$$ and, at most, one different character.More formally, find the length of the shortest string $$$k$$$ such that $$$c = \underbrace{k + \cdots + k}_{x\rm\ \text{times}}$$$ for some positive integer $$$x$$$, strings $$$s$$$ and $$$c$$$ has the same length and $$$c_i \neq s_i$$$ for at most one $$$i$$$ (i.e. there exist $$$0$$$ or $$$1$$$ such positions).

Input: The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — the number of test cases.The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — the length of string $$$s$$$.The second line of each test case contains the string $$$s$$$, consisting of lowercase Latin characters.The sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output: For each test case, print the length of the shortest string $$$k$$$ satisfying the constraints in the statement.

Note: In the first test case, you can select $$$k = \texttt{a}$$$ and $$$k+k+k+k = \texttt{aaaa}$$$, which only differs from $$$s$$$ in the second position.In the second test case, you cannot select $$$k$$$ of length one or two. We can have $$$k = \texttt{abba}$$$, which is equal to $$$s$$$.

Sample Inputs:
5
4
abaa
4
abba
13
slavicgslavic
8
hshahaha
20
stormflamestornflame

Sample Outputs:
1
4
13
2
10

Solution (Python):
from collections import defaultdict

def fun(n, s):
    l = []
    i = 1
    while i * i <= n:
        if n % i == 0:
            l.append(i)
            if i != n // i:
                l.append(n // i)
        i += 1
    l.sort()
    for i in l:
        f = defaultdict(int)
        chk = True
        for j in range(0, n - i + 1, i):
            f[s[j:j + i]] += 1
            if len(f) > 2:
                chk = False
                break
        if chk:
            if len(f) == 1:
                return i
            (a, b) = ([], [])
            for ii in f:
                a.append(ii)
                b.append(f[ii])
            if 1 in b:
                (c, d) = a
                diff = sum((1 for (a, b) in zip(c, d) if a != b))
                if diff == 1:
                    return i
    return n
tc = int(input())
for _ in range(tc):
    n = int(input())
    s = input()
    x = fun(n, s)
    print(x)

Solution (Python):
from collections import defaultdict

def solve():
    n = int(input())
    s = input()
    for step in range(1, n + 1):
        if n % step == 0:
            a = defaultdict(int)
            for i in range(0, n, step):
                a[s[i:i + step]] += 1
            if len(a.keys()) == 1:
                print(step)
                return
            if len(a.keys()) == 2:
                (v1, v2) = a.keys()
                if a[v1] == 1 or a[v2] == 1:
                    c = 0
                    for v in range(len(v1)):
                        if v1[v] != v2[v]:
                            c += 1
                        if c > 1:
                            break
                    if c == 1:
                        print(step)
                        return
for _ in range(int(input())):
    solve()

Solution (Python):
from collections import defaultdict

def solve():
    n = int(input())
    s = input()
    for i in range(1, n + 1):
        if n % i == 0:
            a = defaultdict(int)
            for j in range(0, n, i):
                a[s[j:j + i]] += 1
            if len(a.items()) == 1:
                print(i)
                break
            if len(a.items()) == 2:
                (v1, v2) = a.items()
                if v1[1] == 1 or v2[1] == 1:
                    flag = 0
                    for k in range(len(v1[0])):
                        if v1[0][k] != v2[0][k]:
                            flag += 1
                    if flag == 1:
                        print(i)
                        break
for _ in range(int(input())):
    solve()