Strings in Memory & Immutability

A string is an array with a lock on it

Recall the train of coupled cars from the Arrays module — a string is that exact same train, one character per car, except now every car is welded shut. You can walk up to car i and look inside (s[i] is a perfectly ordinary O(1) read), but you can never swap out what's in it. Under the hood, a string is an array of character units — contiguous, O(1)-indexable, scannable with everything you learned in the Arrays module. One property changes the game: in both course languages, strings are immutable. You can read s[i]; you cannot assign to it. Every "modification" — replace, upper, concatenation — allocates a new string and copies: not a weld cut open, but an entirely new train built car-by-car to match what you asked for.

Why language designers lock strings: safe sharing (many variables can point at one string with no defensive copies), hashability (a dict/Map key must never change under the table — the Hash Tables module depends on this), and interning optimizations. The price is that mutation-shaped code costs allocation-shaped money.

The classic trap: concatenation in a loop

def join_bad(words: list[str]) -> str:
    result = ""
    for w in words:
        result += w          # allocates a NEW string of len(result) + len(w)
    return result

def join_good(words: list[str]) -> str:
    parts = []               # list of pieces — a dynamic array
    for w in words:
        parts.append(w)      # O(1) amortized
    return "".join(parts)    # one O(total) concatenation at the end

Trace it on four single-character words — ["a", "b", "c", "d"] — and count every character copy join_bad performs:

Ten copies to join four one-character words — join_bad welds together a brand-new, slightly-longer train from scratch on every single word, re-building every car it already had. join_good never copies a character while appending — parts.append(w) stores a reference to w, not its characters, at O(1) amortized each. The only character-copying happens once, at the very end: "".join(parts) allocates a string of the full length (4) and copies each word's characters into it exactly once — 4 copies total, against join_bad's 10, and the gap only widens as n grows. For n words of length L, join_bad re-copies the accumulated prefix on every step: L + 2L + ⋯ + nL = L · n(n+1)/2 character copies — the triangular sum again, O(n² · L). join_good is the dynamic array from Module 4 wearing a disguise: append references (O(1) amortized), pay the character-copy cost exactly once, O(n · L). This "builder" pattern is the string module's single most important habit.

Honesty note: CPython and V8 both special-case += on strings when the reference is private, often making it effectively linear in practice. Rely on that and your code's cost depends on interpreter internals and can degrade back to O(n²) (e.g., prepending, or holding another reference). The builder is the version whose cost you can prove.

Working mutably: the char-array detour

When an algorithm genuinely wants in-place surgery (reversal, two-pointer swaps), convert once, work in the mutable array, convert back:

def reverse_string(s: str) -> str:
    chars = list(s)                      # O(n) once
    left, right = 0, len(chars) - 1
    while left < right:                  # converging pointers — Module 4
        chars[left], chars[right] = chars[right], chars[left]
        left, right = left + 1, right - 1
    return "".join(chars)                # O(n) once

Three sequential phases, each O(n): convert to array, mutate in place, convert back. O(n) + O(n) + O(n) = O(n) — sequence adds, it doesn't multiply, so bracketing an O(n) algorithm with two O(n) conversions is still O(n) overall. (When a problem hands you chars: list[str] / string[] directly, skip the conversions and you have true O(1) auxiliary space.)

The encoding footnote that occasionally bites

"Character" is fuzzier than it looks. JS strings are sequences of UTF-16 code units: "🚀".length === 2, and s[i] can land mid-emoji. Python 3 strings are sequences of code points: len("🚀") == 1. For this course's problems (ASCII inputs, stated in constraints) the distinction is invisible — but when constraints say "lowercase English letters," that's the promise that makes s[i]-based logic and 26-slot count arrays (next lesson) safe.