Take the smallest integer \(M\) that is a divisor of \(N\) and satisfies \(S_i = S_{i+M} = \dots = S_{N-M+i}\) for each \(1 \le i \le M\). Since the proposition is true for \(M=N\), such an \(M\) always exists.

Then, we have \(f(S) = M\). Below, we will try to minimize \(M\).

For each divisor \(M\) of \(N\), let us determine whether we can make \(f(S) = M\). This can be done in \(\mathrm{O}(|S|)\) time, since for each \(1 \le i \le M\), it is optimal to make \(S_i,S_{i+M},\dots,S_{N-M+i}\) fit the majority.

Since \(N\) has at most \(N\) divisors, the problem has been solved in \(\mathrm{O}(N^2)\) time. Actually, \(N\) has at most \(\sqrt N\) divisors less than or equal to \(N\), so the same method works when \(N \le 2 \times 10^5\).