:3

@olee2002 It's good that you benchmarked it! There are a couple possibilities.

1. Microbenchmarks in Java are notoriously difficult.

2. As you suggested, the O(n^2) version could very well be faster for small n.

Note that strings in Javascript are also immutable, so you get the same situation. The solution is less clear, but I think string.join is an O(n) solution in JS. "Naive" concatenation with + in JS may use something like StringBuilder under the hood depending on the browser engine (but I wouldn't count on it), whereas in Java it's guaranteed to be O(n^2).

This solution does not complete in time when I run it.

Hello!

I don't know if solving it in this way has a name. Maybe constraint satisfaction?

I think it is one natural way of approaching optimization for the problem: constrain the next subset to be explored based on the current subset.

It doesn't modify the input. string.toLowerCase returns a new string, and assigning it to string only modifies the local variable string. Anyway, Javascript strings are immutable so you can't modify the input.

You could say that it's bad to re-use parameters in this way, but that's different from modifying the argument, which implies side effects.

I agree that the performance could be better, although this is actually asymptotically optimal O(n). It is O(26 * n) = O(n).

I agree that this solution is not best. It matches the requirement but only because of the constrained input. It would have been just as easy to match the text of the requirement and ignore the constraint, and in a real solution that would probably be more robust in case more inputs were introduced.

Split on digits: O(n)

Map on pow: O(n)

Filter: O(n)

Reverse: O(n)

Join: O(n) (note that solutions which iterate might end up being O(n^2) if they don't join right)

Speed is not a valid complaint about this solution, because you aren't going to beat O(n). (If you want to get really technical, all optimal solutions are O(n log n) because you will be printing logn digits n times).

Functional tools like map are very standard now and should be familiar to anyone using the language seriously. The only part of this answer that is tricky is the use of split(''), but this is a pretty common trick for getting an array of characters (as Javascript unfortunately won't treat strings as mappable collections). join is used in a plain way. The implicit conversions from string to int are a little weird.

Better to extract the inner function to prevent deep nesting IMO.

Sneaky snake

Sorry, I'll watch that in the future.