Find which term is repeated in a string, when given a known number of N occurrences in the string

Question

Is there a way to do the following, without using brute force or something like that?

str = "abbcccddddefefef"
N = 3
repeated_term = func(str,N)

print(repeated_term )
> ['c','ef']

N = 2
term = func(str,N)

print(term)
> ['b', 'dd', 'fe']

*********
Thanks!

Answer 1

Best I can come up with is generating all possible substrings and simply checking.

If your string is length L and you are checking for N repetitions, you don't need to generate substrings larger than L/N, (or even (L-i)/N if you are at the i-th position), because longer strings have no space to repeat.
And if you find a match you can skip ahead L*(match length) characters.

That's a decent O(n²) algorithm at least.

You could study the LZ77 algorithm to come up with something better I'm sure. But I'm not too familiar with it.

Answer 2

Do you know that all occurrences happen in sequence?
In other words, is `func("defefdefd", 3) == ["ef", "d"]`?

Also, is `func("ab", 1) == ["a","b","ab"]` or just `["ab"]`?

Answer 3

Yes, they should be in sequence.