Seems like all the solutions here are really n^4. The only possible way I can see an n^3 solution is if you preprocess the original string to find all equal sub strings via hashing.

There's O(n^2) sub problems for each substring.

When you want to see if a string can be broken up into 'k' parts, you need to potentially try breaking the string up into 1, 2, 3... k parts. This is an O(n) loop. (Actually, perhaps this is really a sqrt(n) loop since you only have to try divisors up to the sqrt(n).. so perhaps we can get O(n^3*sqrt(n))

To check if all 'k' parts are equal takes O(n) time. So in total, it would take O(n^4)... am I missing something?