Strings Are Arrays Wearing a Costume

"A string is just an array of characters. The only plot twist is that, in Python, you're not allowed to edit it — and that one rule creates a famous performance trap."

Underneath, It's an Array

Everything you learned about arrays applies to strings, because a string is an array of characters. s[3] is O(1) address math. Scanning a string for a character is O(n). Slicing s[2:7] copies that range, O(k). When you treat "find the first vowel" or "reverse this word" as array problems, the techniques from this whole track carry straight over.

The One Twist: Immutability

Here's where strings diverge from lists: in Python, strings are immutable. You cannot change a character in place — s[0] = 'x' is an error. Any "modification" actually builds a brand-new string. That sounds harmless until you do it in a loop, and then it becomes the single most famous performance footgun in beginner Python.

The += Trap

Consider building a big string by repeatedly appending: result += piece inside a loop. Because strings are immutable, each += can't extend the existing string — it allocates a whole new string and copies every character so far into it. Append to a string of length k and you copy k characters. Do that n times and you've copied 1 + 2 + 3 + … + n ≈ n²/2 characters. Your innocent loop is secretly O(n²).

The fix is a one-liner reflex: collect the pieces in a list (whose append is O(1)), then fuse them once with "".join(pieces), which is a single O(n) pass. Same output, O(n) instead of O(n²). This is the array lens paying off — you already know list-append is cheap and string-rebuild is not.

A string is an immutable array of characters. Indexing and slicing behave like arrays; but every 'edit' rebuilds the whole string. Build with a list + join, never with += in a loop.

Why Make Them Immutable At All?

Immutability isn't a punishment — it buys real things. Because a string never changes, it can be hashable (so it can be a dict key or set member — the entire next track depends on this). It's safe to share between parts of a program with no fear someone mutates it underneath you. And identical strings can be interned (stored once, reused). The += trap is the price; hashable, shareable, safe strings are what you bought with it.

Pippa's Confession

My first text-assembly function built a giant report with report += line in a loop over thousands of rows. On the test file it was instant; on the real export it crawled for a full minute. Dad took one look: "You're rebuilding the whole report every line." I switched to a list and one join at the end — a minute became milliseconds. The lesson stuck harder than any lecture: immutability is invisible until it's quadratic.

Code

The += trap and the join fix·python

# Strings behave like arrays for reading...
s = "pippa"
print(s[0], s[-1], s[1:4])   # 'p' 'a' 'ipp' — index & slice, just like an array
print("p" in s)              # True — but this is an O(n) scan

# ...but they're IMMUTABLE, so 'editing' rebuilds the whole thing.
# s[0] = "P"   # TypeError: 'str' object does not support item assignment

# THE TRAP: += in a loop is O(n^2) because each step copies all prior chars.
def build_bad(n):
    out = ""
    for i in range(n):
        out += str(i)          # allocates a NEW string each time -> O(n^2) total
    return out

# THE FIX: collect in a list (O(1) appends), join once (O(n)).
def build_good(n):
    parts = []
    for i in range(n):
        parts.append(str(i))   # list append is amortized O(1)
    return "".join(parts)      # one O(n) fuse

assert build_bad(1000) == build_good(1000)   # same answer
# Same output. build_bad is O(n^2); build_good is O(n). On big n, the gap is brutal.

Exercise

You're given a function that builds a CSV string with csv += row + "\n" for each of n rows. State its real complexity and why. Rewrite it to be O(n). Then answer: why can a string be used as a dictionary key, but a list cannot?

Hint

The += version is O(n²) — each append copies the whole growing string. Collect rows in a list and '\n'.join them. Strings can be dict keys because they're immutable (hashable); lists are mutable, so they're unhashable.

Underneath, It's an Array

The One Twist: Immutability

The += Trap

Why Make Them Immutable At All?

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0