• Ranks cannot be changed, but I totally agree, it's a bit too easy for a 6 kyu. A small bit of math would do the trick well.

  • do you mean something different from the worst case or what?

    Yeah, I messed it up. I calculated the repeated string concatenation as T(n) = n^2 as in the worst case, but comparisons as T(n) = 1 as in "more realistic" scenario (i.e. you're unlikely to deal with GigaByte-sized strings, and the constant factor is so low, the O(n) comparsion can be negligible). This particular solution is indeed O(n^3)

    What is n?

    In the worst scenario all the inputs' sizes are inifinitely big, so both the string and the list will be n, no?

  • while it could be O(len(s)) by using a set

    With hashing a newly created string - yes.

    So the final algorithm is O(len(s) ** 2 * len(l))

    Looks correct to me for the worst case.

    O(len(l)) for creating the set

    Only if the hashes are already calculated and cached; otherwise len(l[i]) has to be somewhere as well.

    This solution is O(n^2)

    What is n? And do you mean something different from the worst case or what? Arbitrary strings can't be compared in O(1).

  • So the final algorithm is O(len(s) ** 2 * len(l)) instead of the O(max(len(l), len(s) ** 2))

    That's not how O works, and your reasoning is wrong too. This solution is O(n^2), and there's no asymptotically better algorithm for this task.

  • This comment is hidden because it contains spoiler information about the solution

  • I did but this expression has many interpretations and I wanted to know yours.
    Thanks for your kindness.

  • So here comes my first suggestion: Hankuna matata!

    I don't understand... Say it in English:-)

  • Sorry, it is a suggestion, not an issue... Nevertheless I added it.
    Please verify and stop with suggestions:-) CW is so slow that it takes times to re-publish and most often it times out when re-publishing.

  • Added though without any interest since everybody already knows the answer:-)

  • I find 5 kyu about right. Oh, and thanks for the compliment!

  • I did not look up the implementation of 'all' in cpython, but my tests show that all seems to end when one 'False' is found.
    So no, i think this is pretty efficient, as he is passing an iterator not a list to all.

    EDIT: Buildin all indeed breaks if it encounters a false, see: 1