Modifying Strings: Inserting, Deleting, and Replacing Characters

By now you have established the understanding that strings in Python are immutable and that every operation which appears to modify a string is actually producing a new one. That raises a practical question that needs a direct answer: if strings cannot be changed in place, how does one actually perform the kinds of modifications that real programs and algorithms constantly require? Inserting a character at a specific position, removing an unwanted character, replacing one substring with another, these are fundamental operations, and understanding how to perform them correctly and efficiently is what we’ll learn now.

Inserting a character

Inserting a character at a specific position means placing a new character at a given index and shifting every character from that position onward one step to the right to accommodate it.

Consider the string "helo" and the requirement to insert the character 'l' at index 3.

The character 'o' that was at index 3 has moved to index 4 to make room for the inserted character. In general, inserting at position $i$ requires shifting every character from index $i$ to the end of the string one position to the right. In the worst case, inserting at the beginning of the string requires shifting all $n$ existing characters, making insertion an $O(n)$ operation.

Insertion method 1

In Python, as strings are immutable, insertion is implemented by converting the string to a list of characters, performing the insertion on the list, and joining the result back into a string. The insert(i, x) method places the element x at index i, shifting all subsequent elements one position to the right.

The list conversion costs $O(n)$ ...