Some googling suggests that when you concatenate or take a substring of a Java string, it makes a copy. This takes O(n) time, like iterating over all the characters. Maybe you could avoid this by casting to a char array and then mutating it, but that is not idiomatic to Clojure.

O(n^2) because the for comprehension generates a cartesian product of the numbers vector with itself (or more specifically in this case, the indices of the numbers vector)

What is the runtime complexity for this algorithm?

Wouldn't using frequencies instead of sort be better in terms of runtime complexity? It is my understanding that sort uses tim-sort---and thus is in O(n * log(n))---while frequencies is in O(n).

A reference solution.

Note that the task asks to produce an array (read: vector), and this will return a seq. Tests pass nonetheless. Rant mode off.

The problem with this solution (performance-wise) is that you "iterate" over the number of characters instead of the number of indexes to change. Therefore, for a very large string, you would be doing a lot of operations, even if the number of indexes to change is low.