PYTHON / STRINGS
String immutability and concatenation cost
Explain why a str can never be edited in place, predict the quadratic cost of += in a loop, and build strings with a list plus join instead.
What you will learn
- Recognise that every str method returns a new object and leaves the original untouched
- Count the characters copied by a += loop and see why the total grows like n squared
- Replace accumulation loops with list.append plus ''.join, or with io.StringIO
- Rebuild a modified string via slicing or list(s) instead of item assignment
Understanding String immutability and concatenation cost
A Python str is fixed the moment it is created: its length and its characters are baked into the object. That is why s[0] = 'A' raises TypeError instead of editing the first character, and why s.upper(), s.replace(...) and s.strip() all hand back a brand new string while the one you called them on stays exactly as it was. The useful mental model is that a string is a sealed block of characters and a variable is only a label pointing at it; assignment moves the label, it never rewrites the block.
That guarantee has a price. Because there is no way to extend a string in place, a + b must allocate room for len(a) + len(b) characters and copy both operands into it. Inside a loop the left operand is the text accumulated so far, so pass k copies roughly k characters, and the copies sum to about n squared over two. Ten times more input therefore means about a hundred times more copying, which is why a += loop that feels instant on 50 items can stall for minutes on a million.
The fix is to stop growing an immutable object and instead collect the pieces somewhere that really is mutable. Appending to a list is amortised constant time and never touches the text already stored, and a single ''.join(pieces) walks the list once to compute the total length, allocates one buffer, and copies each piece exactly once. io.StringIO does the same job for code that writes output incrementally. Immutability is not a design flaw here: it is what lets strings be hashed, used as dict keys, interned, and shared between threads without defensive copying.
s = "abc"
try:
s[0] = "A" # strings have no item assignment
except TypeError as err:
print("assign failed:", err)
upper = s.upper() # a new object, s is unchanged
print(s, upper, s is upper)
total_copied = 0
acc = ""
for word in ["red", "green", "blue"]:
total_copied += len(acc) + len(word) # size of the object += must build
acc += word
print(acc, len(acc), total_copied)
# join builds the same 12 characters with one allocation and one copy each
print("".join(["red", "green", "blue"]) == acc)A str can never be modified in place, so each concatenation allocates and copies, which turns repeated += into quadratic work.
Worked examples
Measuring the quadratic growth
Counts the characters that += must copy to build an n-character string, showing the total is n(n+1)/2.
def chars_copied(n):
total = 0
acc = ""
for _ in range(n):
total += len(acc) + 1 # every += allocates this many characters
acc += "x"
return total
for n in (10, 100, 1000):
print(n, chars_copied(n), n * (n + 1) // 2)Example explained
Line 1len(acc) + 1 is the exact size of the new string object each += has to allocate and fill.
Line 2The counted total matches n(n+1)//2 exactly, which is the closed form of 1+2+...+n.
Line 3Going from n=100 to n=1000 multiplies the input by 10 but the copying by about 100.
Line 4Building the same 1000 characters with ''.join would copy 1000 characters, not 500500.
Changing one character
Three ways to get a modified string, and the one built-in type that really does support in-place edits.
name = "jupiter"
fixed = name[0].upper() + name[1:] # build a new string from slices
print(name, fixed)
chars = list(name) # a mutable copy of the characters
chars[0] = "J"
print("".join(chars))
buf = bytearray(b"jupiter") # bytearray is mutable, str is not
buf[0] = ord("J")
print(buf.decode(), len(buf))Example explained
Line 1name still prints as 'jupiter': slicing read from it, it was never altered.
Line 2list(name) copies the characters into a list, which does support chars[0] = 'J'.
Line 3buf[0] = ord('J') writes one byte inside the existing bytearray, so no new object is created.
Line 4len(buf) stays 7, confirming the bytearray was patched rather than rebuilt.
Accumulating without copying
The two standard replacements for a += loop: a list of pieces joined once, and an io.StringIO buffer.
import io
parts = []
for i in range(4):
parts.append("row " + str(i)) # appending never touches earlier text
print("|".join(parts))
buf = io.StringIO() # a growable text buffer
for i in range(4):
buf.write(str(i))
buf.write(";")
print(buf.getvalue())
print(len(parts), len(buf.getvalue()))Example explained
Line 1parts holds 4 separate small strings; none of them is copied when the next one is appended.
Line 2'|'.join(parts) sums the lengths, allocates once, then copies each piece a single time.
Line 3buf.write appends into an internal buffer, so cost is proportional to the bytes written, not to the length so far.
Line 4getvalue() materialises the final str only once, at the end.
Important notes
CPython sometimes resizes a string in place for x += y when x is a local holding the only reference. That is an unspecified optimisation, it disappears as soon as another name, list, or slice also refers to the string, and other implementations need not do it, so never design around it.
Do not use is or id() to prove a copy happened: short literals are often interned and shared, so identity comparisons on strings tell you about interning, not about immutability.
Common mistakes
Calling s.replace('a', 'b') or s.strip() without assigning the result, then wondering why s is unchanged: the new string was created and immediately thrown away.
Using text += line inside a loop over a large file or list; it looks fine on 100 items and degrades quadratically, so a million lines can take minutes of pure copying.
Trying s[0:1] = 'A' after item assignment fails, expecting slice assignment to work as it does on lists; strings support neither, and both raise TypeError.
Try it yourself
Change, predict, then run
Build the string "0123..." for n = 20000 twice, once with result += str(i % 10) in a loop and once by appending to a list and joining at the end; assert the two results are equal and print both durations measured with time.perf_counter.
Open the Python workspaceCheck your understanding
You append one character at a time to a string with s += c inside a loop that runs n times. Why does the total work grow roughly like n squared rather than n?
- Each += must allocate a new string and copy every character accumulated so far, so the copies sum to about n squared over two
- Each += calls a Python-level __add__ method, and the per-call overhead of n function calls dominates the runtime
- Python re-hashes and interns the whole string after every concatenation so it can be reused as a dict key
- Each character lives in its own object and the loop has to re-link all of them on every pass
Show answer
The cost is memory copying: since a str cannot grow in place, pass k rebuilds a string of length k, and 1+2+...+n is about n squared over two. Option two is tempting because n function calls sound expensive, but str.__add__ is C code and the call overhead is linear in n; it is the copying, not the calling, that scales quadratically.