正整数 \(M\) のうち、\(N\) の約数でありかつ \(1 \le i \le M\) に対して \(S_i = S_{i+M} = \dots = S_{N-M+i}\) が成り立つ最小の整数 \(M\) を取ります。\(M=N\) で上記の命題は成り立つため、必ずそのような \(M\) を取ることができます。

この時、\(f(S) = M\) となります。以降 \(M\) を最小化することを考えます。

\(N\) の約数 \(M\) 全てに対して \(f(S) = M\) とすることが可能かを判定します。これは \(1 \le i \le M\) に対し \(S_i,S_{i+M},\dots,S_{N-M+i}\) を最も多いものに揃えればよいため、\(\mathrm{O}(|S|)\) で判定可能です。

\(N\) の約数の個数は \(N\) 以下であるため、この問題を \(\mathrm{O}(N^2)\) で解くことができました。また、\(N\) 以下の約数の個数は実際には \(\mathrm{O}(\sqrt N)\) であるため同じ解法で \(N \le 2 \times 10^5\) でも解くことができます。