Aren't all these solutions posted here O(n^4)?


  • 1
    J

    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?


  • 0
    J

    Actually, it looks like many of the solutions are using the (s+s).find(s, 1, -1) trick to avoid trying each possible number of ways there are to split a string into "k" equal parts.


  • 0
    S

    You could still get O(N^3) with this approach if you use a set to determine whether all k parts are equal


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.