Is there a way to insert a character at multiple indices in one pass?

Question

I have a string and I want to insert a specific character, \n for example, at many indices, which I have stored in a List. Is there an efficient way of modifying the string without first splitting it? I care more about time than space in this case.

If this helps, the function is within a Singleton class, and is being used to reformat the string which will then be rendered to a game scene upon return (this for a game in Unity).

Answer 1

A first version could be this:

public static string InsertStringAt(string str, int[] indexes, string insert)
{
    if (indexes.Length == 0 || insert.Length == 0)
    {
        return str;
    }

    var sb = new StringBuilder(str.Length + indexes.Length * insert.Length);

    int ixIndexes = 0;

    // We NEED ordered indexes
    // We don't order "in place" indexes because it is bad
    // modifying input parameters
    var indexes2 = indexes.OrderBy(x => x).ToArray();

    int i = 0;

    for (; i < str.Length; i++)
    {
        while (ixIndexes < indexes2.Length && i == indexes2[ixIndexes])
        {
            if (indexes2[ixIndexes] < 0)
            {
                // index < 0
                throw new ArgumentOutOfRangeException(nameof(indexes));
            }

            sb.Append(insert);
            ixIndexes++;
        }

        sb.Append(str[i]);
    }

    while (ixIndexes < indexes2.Length && i == indexes2[ixIndexes])
    {
        if (indexes2[ixIndexes] < 0)
        {
            // index < 0
            throw new ArgumentOutOfRangeException(nameof(indexes));
        }

        sb.Append(insert);
        ixIndexes++;
    }

    if (ixIndexes != indexes2.Length)
    {
        // Some indexes were > indexes.Length
        throw new ArgumentOutOfRangeException(nameof(indexes));
    }

    return sb.ToString();
}

Note that there is a possible optimization, but the optimization will render the code more complex. Instead of adding the chars one at a time, we could add all the substrings of str between the indexes.

Second version... In the end it wasn't more complex:

public static string InsertStringAt(string str, int[] indexes, string insert)
{
    if (indexes.Length == 0 || insert.Length == 0)
    {
        return str;
    }

    var indexes2 = indexes.OrderBy(x => x).ToArray();

    var sb = new StringBuilder(str.Length + indexes.Length * insert.Length);

    int j = 0;

    for (int i = 0; i < indexes2.Length; i++)
    {
        if (indexes2[i] < 0)
        {
            throw new ArgumentOutOfRangeException(nameof(indexes2));
        }

        if (indexes2[i] > str.Length)
        {
            throw new ArgumentOutOfRangeException(nameof(indexes2));
        }

        sb.Append(str, j, indexes2[i] - j);
        sb.Append(insert);

        j = indexes2[i];
    }

    sb.Append(str, j, str.Length - j);

    return sb.ToString();
}

Answer 2

I suggest a string extension method that copies slices between positions into a StringBuilder and inserts the char at each position:

public static class StringExt {
    public static string InsertCharAt(this string src, char ins, IEnumerable<int> poss) {
        var orderedPoss = poss.ToList();
        orderedPoss.Sort();

        var ans = new StringBuilder(src.Length+orderedPoss.Count);

        var srcSpan = src.AsSpan();
        var beginPos = 0;
        foreach (var insPos in orderedPoss) {
            ans.Append(srcSpan.Slice(beginPos, insPos-beginPos));
            ans.Append(ins);
            beginPos = insPos;
        }
        return ans.ToString();
    }
}

NOTE: If you don't have Span, the three argument StringBuilder.Append method can be used instead (as @xanatos did).

PS: Per @pingfloydx33 a single allocation version using String.Create:

public static string InsertCharAt2(this string src, char ins, IEnumerable<int> poss) {
    var orderedPoss = poss.ToList();
    orderedPoss.Sort();

    return String.Create(src.Length + orderedPoss.Count, new { }, (ans, _) => {
        var srcSpan = src.AsSpan();
        var beginPos = 0;
        var writePos = 0;
        foreach (var insPos in orderedPoss) {
            var subLen = insPos-beginPos;
            srcSpan.Slice(beginPos, subLen).CopyTo(ans.Slice(writePos));
            writePos += subLen;
            ans[writePos++] = ins;
            beginPos = insPos;
        }
    });