This can be done optimally in O(n) time by iterating over the string, swapping the character at index i with the character at a random index each time.

It's not possible to do asymptotically better than O(n) because on average you'll have to change n-1 of the characters (assuming they're all distinct).