I have a feeling that the following question might have been studied: Suppose I have a finite alphabet $A,$ with $|A| = n,$ and a string $S$ of length $N.$ A string can be said to contain a $k$-th power, if $$S = S_1 S_2^k S_3,$$ where exponentiation means that $S_2$ is repeated $k$ times, and $S_1$ and $S_3$ might be empty. Let $P(n, N)$ be the function defined by: every string of length $N$ over an alphabet of length $n$ contains a $P(n, N)$-th power. Now, the question(s):

1. What is the (asymptotic) behavior of $P(n, N)?$
2. Given a string $S$ as above, how hard is it to compute whether $S$ contains a $k$-th power?
3. What can one say about random strings?