Function for encoding strings in-place I recently wrote a function that replaces every white space with '%20', just for fun (and sharping my coding skills). The input string is terminated with extra white spaces, with the length that the string should have after encoding takes place. For example:

input = "Not encoded  " //2 white spaces in the end
output = "Not%20encoded"


Although I was able to implement such encoding in-place, I was still not pleased with the result, specially due to the inner loop that shifts the whole string to the right everytime a white space is found. Here is my solution, written in C#:

    public string encode(string str)
    {
        var array = str.ToCharArray();
        for (int i = 0; i &lt; array.Length; i++) {
            if (array[i] != ' ') continue;

            //switch every char &gt;&gt; 2, from the end of the string to i
            for (int j = array.Length - 1; j &gt; i; j--) {
                array[j] = array[j - 2];                    
            }

            array[i++] = '%';
            array[i++] = '2';
            array[i] = '0';
        }
        return new String(array);
    }


I'm looking for a solution that operates in O(n), possibly performing a single traversal on the input string. Additional feedback on how to improve performance/readability of my function are always very appreciated :)
Your solution:


copies the whole string twice (1. string.ToCharArray() 2. new string())
needs n bytes of extra storage (apart from the input and output; n is the size of the output)
potentially moves the characters in the string a lot (O(n2))
requires the input to already have free space for the expansion


Solution using StringBuilder:


copies the whole string twice (1. calls to Append() 2. StringBuilder.ToString())
needs about n bytes of extra storage
doesn't need to move characters at all
doesn't require the input to be in any special format


Based on this, StringBuilder is clearly the better solution.

But there is even better solution: just use string.Replace(). That's likely going to be quite efficient and it's much shorter than any other of the proposed alternatives.