Strings Are Immutable Arrays

Recall from lesson 2-1 what makes word[4] an O(1) read: the characters must be stored contiguously, so the position can be computed with base + i × size.

A string is stored much like an array of characters, one contiguous block with uniform slots.

The same address formula therefore applies, which makes word[i] a single computation rather than a walk from the start of the string. That is worth stating explicitly, because it means everything you learned about array indexing carries straight over to strings.

A string is a frozen array

Under the hood a Python string is an array of characters, so indexing and slicing behave exactly like list indexing and slicing, including the O(k) copy cost of a slice.

Strings add one big rule on top: they are immutable. Once created, a string can never change. Every operation that looks like it edits a string actually builds a brand-new string and leaves the original untouched.

Freezing them buys several things at once. An immutable string can be shared everywhere without defensive copies, since no holder can alter it. It can be cached, and its hash can be computed once and reused, which is what allows strings to serve as dict keys in unit 6. Contents that can never shift under you are contents you can safely build an index on.

The cost of that guarantee is the subject of most of this lesson, because a value that cannot be edited has to be rebuilt.

Immutability, demonstrated twice

Two checks: whether a method mutates the original, and whether assignment into a string is even allowed.

s = "cat"
t = s.upper()
print("t:", t)
print("s:", s)

try:
    s[0] = "b"
except TypeError as e:
    print("error:", e)

Output

t: CAT
s: cat
error: 'str' object does not support item assignment

upper returned a new string and left s as cat, which is the pattern every string method follows. None of them modify in place, so ignoring a method's return value means throwing away its entire effect.

The assignment attempt raises a TypeError rather than failing quietly, which is a genuine kindness. The same line on a list would silently succeed, so Python's refusal here is what keeps the immutability guarantee from being something you can accidentally break.

The accidental O(n²) loop

Immutability comes with a performance trap, and this innocent-looking loop is quadratic.

result = ""
for piece in pieces:
    result = result + piece

Each + has to copy everything built so far plus the new piece, because the old string cannot be extended in place. The copies run 1 character, then 2, then 3, which is the triangle sum from lesson 1-2 and therefore O(n²) in total.

The fix is to stop building the string until the end. Collect the pieces in a list, where append is amortized O(1) from lesson 2-2, then merge once with "".join(parts), which copies each character exactly once for O(n) overall.

Worth noticing how well this trap hides. There is one loop, one operator, and no nested structure anywhere, which is exactly why it survives code review and then surprises someone at scale.

Counting characters copied

Putting numbers on the two approaches, the same way lesson 2-2 compared doubling against growing by one.

def chars_copied_concat(n):
    copied = 0
    length = 0
    for _ in range(n):
        copied += length + 1
        length += 1
    return copied

def chars_copied_join(n):
    return n

for n in [100, 1000, 10000]:
    print(n, chars_copied_concat(n), chars_copied_join(n))

Output

100 5050 100
1000 500500 1000
10000 50005000 10000

In the concatenation version, each pass copies length + 1 characters, the whole string so far plus the new piece, which accumulates into the triangle sum. The join version copies each character exactly once, so the count equals n.

At n = 10,000 the gap is 50 million characters against 10,000, a factor of 5,000. Ten times more input widens the gap by another factor of ten, which is the signature of one growth family outrunning another rather than one being merely slower.

Building one line the fast way

The collect-then-join pattern in its everyday form, assembling a CSV row.

parts = []
for i in range(1, 6):
    parts.append(f"row{i}")
line = ",".join(parts)
print(line)
print("parts appended:", len(parts))

Output

row1,row2,row3,row4,row5
parts appended: 5

The range(1, 6) covers 1 through 5, and each pass appends one small string to the list rather than growing a large one.

",".join(parts) then glues the five parts into a single string with commas between them, which is where the only string construction in the whole routine happens. The separator lives on the left of join, so "".join produces no separator and "\n".join produces lines.

Five items is small enough that either approach would be instant. The reason to write it this way regardless is that the shape of the code stops mattering at 5 and starts mattering at 50,000, and habits do not scale up on demand.

Building a string with result += piece in a loop is O(n²) because strings are immutable, so every += copies the entire string built so far into a new one.

The old string cannot grow in place, which means pass k copies roughly k characters. Summing 1 + 2 + ... + n gives the familiar triangle and therefore quadratic total work.

The remedy is to collect the parts in a list and call "".join once, which is O(n) because each character is copied a single time.

The general lesson generalizes past strings. Whenever a structure cannot be extended in place, repeated small extensions turn into repeated full copies, and the fix is always to batch the work and do the construction once.