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 endoutput = Not%20encodedAlthough 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 < array.Length; i++) {            if (array[i] != ' ') continue;            //switch every char >> 2, from the end of the string to i            for (int j = array.Length - 1; j > 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 :)
Function for encoding strings in-place
c#;performance;strings
As strings are immutable you can't really avoid intermediate store of the data as it's being encoded.As you already know the length of the final string you can avoid the shuffling:    int spaceCount = 0;    for (int i = str.Length - 1; str[i] == ' '; i--)    {        spaceCount++;    }    if (spaceCount == 0) { return str; }    var array = new char[str.Length];    int idx = 0;    for (int i = 0; i < str.Length - spaceCount; i++)    {        var current = str[i];        if (current  == ' ')        {            array[idx++] = '%';            array[idx++] = '2';            array[idx++] = '0';        }        else         {             array[idx++] = current ;        }    }    var encoded = new string(array);Space required is 2 * O(n) (array and final string) and time is 2 * O(n) (encoding string into array, building final string)