Insert a Character at Any Position Without Losing the Original Characters

Insertion increases the length without changing any original character

Start with the string "code" and insert the character 'X' independently in three places. At the first position, the result is "Xcode". At the last position, the result is "codeX". At position 3, the result is "coXde". Each result still contains the original characters 'c', 'o', 'd', and 'e' in the same order.

original:       code   length 4
first position:  Xcode  length 5
last position:   codeX  length 5
position 3:      coXde  length 5

Insertion does not replace the character at the chosen position. For position 3, 'd' is still present in "coXde". The new 'X' goes before it, so the result has five characters instead of four.

A string of length n has n + 1 insertion gaps

The four characters in "code" create five legal gaps: before 'c', between 'c' and 'o', between 'o' and 'd', between 'd' and 'e', and after 'e'. These gaps are numbered as positions 1 through 5. Position 1 is before the first character, position 5 is after the final character, and position 3 is between 'o' and 'd'.

The gap is not a character and does not have a character index of its own. An insertion index tells the string operation how many original characters come before the new character. The gap before 'c' has insertion index 0, while the gap after 'e' has insertion index 4.

A 1-based position k becomes the zero-based insertion index k - 1

For position k, the matching zero-based insertion index is k - 1. With k = 3, the index is 2, so 'X' is inserted after the first two characters, 'c' and 'o'. That produces "coXde". The same mapping gives position 1 to index 0 and position 5 to index 4.

1-based position k     insertion index k - 1     result
1                      0                         Xcode
3                      2                         coXde
5                      4                         codeX

Because a length-4 string has five gaps, valid 1-based insertion positions run from 1 through 5. Position 5 is valid even though there is no character at zero-based index 4 after insertion. Index 4 identifies the gap after the original final character.

C++ and Java use the same insertion index but build the result differently

Both languages use insertion index 2 to place 'X' between 'o' and 'd'. In C++, string::insert changes the copied string directly. In Java, StringBuilder::insert changes the builder, and toString creates the String result. In both cases, copy "code" first, so the original remains unchanged and each insertion can be treated independently.

string original = "code";
string middle = original;

middle.insert(2, 1, 'X');
// middle is "coXde"
// original is still "code"

String original = "code";
StringBuilder middleBuilder = new StringBuilder(original);

middleBuilder.insert(2, 'X');
String middle = middleBuilder.toString();
// middle is "coXde"
// original is still "code"

The first and last results use the same idea with insertion indices 0 and 4. The index changes the gap, not the original character order: index 0 gives "Xcode", index 4 gives "codeX", and index 2 gives "coXde". Each copied result has length 5, while "code" remains length 4.