When you learn about strings, they appear to offer straightforward character-by-character access. Most languages let you retrieve any character instantly: str[5] gives you the sixth character in O(1) time. This suggests modification should be equally simple—just change str[5] to a different character.

But here lies a fundamental asymmetry: reading a character is cheap; writing a character can be expensive.

This page explores why random updates—modifying characters at arbitrary positions—are inefficient in most string implementations, and what this means for algorithm design and problem-solving.

To understand why string updates are expensive, we must first appreciate why reads are cheap, and why the same logic doesn't apply to writes.

Why reading is O(1):

Strings store characters contiguously, enabling direct address calculation:

String: "ALGORITHMS"
Index:   0 1 2 3 4 5 6 7 8 9

To read str[5] (the 'I'):
  address = base_address + 5 × character_size
  return memory[address]

No iteration required. The hardware can jump directly to any memory address. This is random access—the defining feature of contiguous storage.

Why writing is different:

In an immutable string model, you cannot change memory in place. The string object is read-only. To "modify" character 5, you must:

1. Create a new string of the same length
2. Copy characters 0-4 from the original
3. Insert the new character at position 5
4. Copy characters 6-9 from the original
5. Return the new string

Time complexity: O(n) for a single character change.

This is the fundamental asymmetry: reading is O(1), but writing forces O(n) copying.

Let's examine exactly what happens when you try to modify an immutable string. Consider this Python example:

original = "HELLO"
modified = original[:3] + "P" + original[4:]
# modified is now "HELPO"

Step-by-step breakdown:

Total memory touched: 3 + 1 + 4 + 1 + 5 = 14 characters for a 5-character string.

And this is the minimal version. Without slice optimization, intermediate strings bloat memory further.

The cascade of copies:

Now imagine modifying multiple characters in a loop:

text = "AAAAAAAAAA"  # 10 A's
for i in range(len(text)):
    text = text[:i] + "B" + text[i+1:]

Total: 10 × 10 = 100 character operations to produce what should be a trivial in-place transformation.

For a string of length n with k modifications:

• Immutable model: O(k × n) operations
• Ideal in-place model: O(k) operations

When k ≈ n (modifying most characters), the overhead is O(n²) instead of O(n).

Languages with mutable strings (C, C++, Rust) allow in-place modification. You can genuinely change str[5] without copying the entire string. But significant limitations remain.

Simple replacement—the good case:

In C or C++, modifying a character is trivially efficient:

char str[] = "HELLO";
str[4] = 'P';  // Now "HELLP"
// Time: O(1)
// No allocation, no copy

This is the ideal: direct memory manipulation with no overhead.

But insertion and deletion remain O(n):

Even with mutable strings, inserting or deleting characters requires shifting all subsequent content:

Original:  [ H | E | L | L | O ]
Insert 'X' at position 2:

Step 1 - Make room by shifting right:
           [ H | E | L | L | L | O ]  // Copy L, L, O one position right

Step 2 - Insert X:
           [ H | E | X | L | L | O ]

Characters moved: n - i = 5 - 2 = 3

For insertion at position i in a string of length n:

• Best case (insert at end): O(1) if capacity available
• Worst case (insert at beginning): O(n)
• Average case (random position): O(n/2) = O(n)

Modern strings must support Unicode, and Unicode introduces a critical complication: characters have different byte widths.

Fixed-width encodings (UTF-32):

Every character occupies exactly 4 bytes. Character[i] is always at byte position i × 4. Random access and modification are truly O(1)—but at the cost of 4× memory for ASCII text.

Variable-width encodings (UTF-8, UTF-16):

UTF-8 uses 1-4 bytes per character depending on the codepoint:

The problem: character index ≠ byte position

In UTF-8, to find character[i], you must scan from the beginning, counting characters. This makes even reading potentially O(n):

String: "A中B"
Bytes:  [41|E4 B8 AD|42]

character[0] = byte[0] = 'A'       ✓ O(1)
character[1] = byte[1-3] = '中'    Need to scan to find start
character[2] = byte[4] = 'B'       Need to scan past '中' first

Modification becomes even more complex:

Consider replacing a character with one of different width:

Before: "AéB"  →  Bytes: [41|C3 A9|42] (4 bytes total)
           ↑
    Replace 'é' (2 bytes) with '中' (3 bytes)

After:  "A中B"  →  Bytes: [41|E4 B8 AD|42] (5 bytes total)

The replacement requires:

1. Finding the byte position of character 1 (scan from start)
2. Calculating the byte-length difference (+1 byte)
3. Shifting all bytes after position 3 by one position right
4. Writing the new bytes

Even "simple" replacement becomes O(n).

This is why languages like Python3 and modern JavaScript abstract away byte positions entirely—they hide this complexity but don't eliminate it. Under the hood, modifications may trigger copying and reallocation.

The inefficiency of random updates profoundly affects how we design string algorithms. Many approaches that seem natural are actually performance traps.

Example 1: In-place character swapping

Consider reversing a string by swapping characters from both ends:

logical operation:
swap(str[0], str[n-1])
swap(str[1], str[n-2])
...

Expected complexity: O(n/2) = O(n)
Actual complexity in immutable model: O(n²)

Each swap in an immutable language creates a new string, copying n characters. The "efficient" O(n) algorithm becomes O(n²).

Solution: Convert to a mutable structure (character array/list), perform swaps, convert back:

# Instead of:
for i in range(len(s)//2):
    # swap s[i] and s[n-1-i] -- each creates new string!

# Do:
chars = list(s)           # O(n) - one time
for i in range(len(s)//2):
    chars[i], chars[n-1-i] = chars[n-1-i], chars[i]  # O(1) each
result = ''.join(chars)   # O(n) - one time

# Total: O(n) instead of O(n²)

Example 2: Removing characters by condition

Remove all vowels from a string:

# Naive immutable approach:
for char in s:
    if char in 'aeiouAEIOU':
        s = s.replace(char, '', 1)  # O(n) per removal
# Total: O(n × k) where k = number of removals, worst case O(n²)

# Efficient approach:
result = ''.join(char for char in s if char not in 'aeiouAEIOU')
# Total: O(n) - single pass, single allocation

Example 3: Replacing multiple substrings

# Chained replacements (each is O(n)):
text = text.replace("foo", "bar")
text = text.replace("baz", "qux")
text = text.replace("old", "new")
# Total: O(3n) = O(n) but 3 full passes

# For many replacements, consider:
# - Regular expressions with compiled patterns
# - Building output incrementally with a list
# - Using a trie for multi-pattern replacement

Understanding the limitations helps you avoid common performance traps. Here are patterns that frequently cause problems:

Pitfall 1: Modifying strings in loops

This pattern appears innocuous but is quadratic:

result = text
for char in chars_to_remove:
    result = result.replace(char, '')  # O(n) per iteration

Pitfall 2: Character-by-character construction

result = ''
for char in source:
    if some_condition(char):
        result += transform(char)  # O(k) where k = current length

Pitfall 3: Recursive string building

def process(s):
    if base_case:
        return s
    return process(s + modification)  # Each level copies the growing string

Recognition and refactoring:

When you identify these patterns, consider:

1. Collect-then-join: Build a list of pieces, join once at the end
2. Filter-and-construct: Generate results in a single pass using comprehensions or generators
3. Mutable intermediates: Convert to array/list, modify, convert back
4. Streaming output: Write directly to output streams instead of building intermediate strings

Not every application suffers from string update costs. Context determines impact.

High-impact scenarios:

Lower-impact scenarios:

• Read-mostly text processing: Searching, matching, and analyzing without modification
• Short strings: The O(n) cost is negligible when n is small
• Infrequent modifications: One-time transformations during initialization
• Batch processing with efficient patterns: Using join/filter/map instead of loops

We've explored the second major limitation of strings: the inefficiency of random updates. Let's consolidate what we've learned:

What's next:

We've seen how strings struggle with resizing and random updates. But there's another limitation that operates at a different level: strings are designed for text. In the next page, we'll explore why strings are a poor fit for numeric or homogeneous data—and why this matters for algorithm design.