Strings Are Arrays Wearing a Costume

"Strings are close enough to arrays to borrow their best tricks—but Python str is an immutable Unicode sequence, and that plot twist creates the famous += performance trap. Treat it as merely a character array and it bites."

Underneath, It's an Array

Strings share sequence operations with arrays, so indexing, scanning, slicing, and two-pointer reasoning often transfer. But Python str is a Unicode sequence whose internal representation is not simply a fixed-width character array. Use the language's operation contracts rather than assuming a C-style layout.

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

Repeated result += piece may rebuild and copy a growing immutable value, so the general cost model can reach O(n²). CPython can optimize some concatenations depending on reference state, but the language does not promise that behavior. Do not base a large string builder on that implementation accident.

The predictable default is to collect pieces in a list and combine them once with "".join(pieces). A handful of small concatenations is fine; for many pieces, join makes both intent and total-work reasoning clearer.

A Python string is an immutable Unicode sequence, not simply a fixed-width character array. Repeated edits may rebuild growing values; for many pieces, collect them and join once.

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

Repeated += can be O(n²) because it may copy a growing immutable value. 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