Fastest Sorted String Concatenation

What is the fastest and most efficient way to do this: word = 'dinosaur' newWord = word[0] + ''.join(sorted(word[1:])) output: 'dainorsu' Thoughts: Would something as converting

Solution 1:

Here's how I'd approach it.

Create an array of size 26 (assuming that only lowercase letters are used). Then iterate through each character in the string. For the 1st letter of the alphabet, increment the 1st index of the array; for the 2nd, increment the 2nd. Once you've scanned the whole string (which is of complexity O(n)) you will be able to reconstruct it afterwards by repeating the 'a' array[0] times, 'b' array[1] times, and so on.

This approach would beat a fast sort algorithm like quicksort or partition sort, which have complexity O(nlogn).

EDIT: Finally you'd also want to reassemble the final string efficiently. The string concatenation provided by some languages using the + operator can be inefficient, so consider using an efficient string builder class.