Strings in Python: Immutability, += vs join, and Hidden Copies

A Python string looks like a list of characters, and you can index it, slice it and loop over it like one. But you cannot change it. Every operation that seems to edit a string, from upper() to +=, hands back a brand-new string and leaves the old one exactly as it was. That single rule, immutability, is behind the most common accidental O(n²) in Python and behind a handful of interview follow-ups worth knowing cold.

The problem it solves

Immutability buys safety. A string can be shared by any number of variables, used as a dictionary key or passed to a function without anyone worrying that it will change underneath them, and its hash can be cached.

The cost appears when you build a string piece by piece. If a string cannot grow, then out += piece has to create a new string holding everything in out plus the piece, and copying everything in out is the expensive part. Do that in a loop and each step copies more than the last: 1 character, then 2, then 3. The copies add up to about n²/2 for n characters, so a loop that looks linear is quadratic.

The intuition

Four rules cover nearly everything:

1. No item assignment. s[0] = "S" raises TypeError. Build a new string instead: "S" + s[1:].
2. Every "edit" returns a new string. upper(), replace(), strip() and slicing never change the original, so s.upper() on its own line does nothing useful; write s = s.upper().
3. Collect, then join once. Append pieces to a list, where appends are O(1) amortised, then call "".join(parts), which measures the total length, allocates once and copies each character exactly once.
4. Slices copy. s[i:j] costs O(j - i). Slicing inside a loop or a recursion, as in is_pal(s[1:-1]), quietly multiplies the work; pass indexes instead.

One honest caveat: CPython can sometimes grow a string in place when nothing else refers to it, which hides the quadratic cost of += in simple loops. That is an implementation detail, not a promise of the language. PEP 8 explicitly says not to rely on it (from memory), other interpreters do not do it, and a single extra reference switches it off. The measurement below shows both sides.

Watch it run

The animation builds STRING one character at a time, two ways, because a Python string cannot be edited in place. S starts both versions: one new string of length 1, and one list holding one character. Python offers no way to edit a string, so += T in general copies what is already there into a fresh one. Again for R: two characters re-copied, while append touches nothing that is already down. The copy bill is now 10 characters for 4 appended, and it is still growing faster than the string. Adding N rewrites the whole result again, so the cost of step k is k characters. Six characters have cost 21 copies; at n characters it is about n²/2, a quietly quadratic loop. One join at the end copies each character exactly once: the whole build is O(n). The last frame puts them side by side: identical output, a different complexity class, 21 copies against 6.

The code

Immutability first, then a toy model of the copying cost under the general rule that every += builds a fresh string:

import random
import time
import unicodedata

s = "string"
t = s                                    # a second name for the same string
try:
    s[0] = "S"
except TypeError as e:
    print(type(e).__name__)              # TypeError
s = s.upper()                            # a new string; the old one is untouched
print(s, t)                              # STRING string

def copies_concat(pieces):
    """Characters copied if every += builds a fresh string (the general model)."""
    total, length = 0, 0
    for p in pieces:
        length += len(p)
        total += length                  # old characters re-copied, plus the new ones
    return total

def copies_join(pieces):
    return sum(len(p) for p in pieces)   # each character copied exactly once

chars = list("STRING")
print(copies_concat(chars), copies_join(chars))           # 21 6
lines = ["x" * 100] * 10_000
print(copies_concat(lines), copies_join(lines))           # 5000500000 1000000

The lesson's six characters cost 21 copies against 6. Ten thousand 100-character log lines, the lesson's real-world example, cost five billion character copies against one million. Now what CPython actually does. The same loop is timed three ways: plain +=, += while another reference to the growing string exists, and join:

def timed(build, n):
    start = time.perf_counter()
    build(n)
    return time.perf_counter() - start

def plus_equals(n):
    out = ""
    for _ in range(n):
        out += "x" * 10
    return out

def plus_equals_shared(n):
    out, history = "", []
    for _ in range(n):
        history.append(out)              # a second reference to the current string
        out += "x" * 10
    return out

def joined(n):
    return "".join("x" * 10 for _ in range(n))

plain, shared, join = (timed(f, 20_000) for f in (plus_equals, plus_equals_shared, joined))
print(shared > 10 * plain, shared > 10 * join)          # True True

Plain += was fast here because CPython resized the string in place; once the old string is still referenced it must copy, and the same loop is more than ten times slower (hundreds of times on the machine used for this article). join is fast either way. Next, a trap that has nothing to do with speed: Unicode. The same visible word can be stored two ways:

composed, decomposed = "café", "café"
print(composed == decomposed, len(composed), len(decomposed))   # False 4 5
nfc = unicodedata.normalize("NFC", decomposed)
print(nfc == composed, len(nfc))                         # True 4

Both print as "café", yet they compare unequal and have different lengths, because one uses a single code point for é and the other uses e plus a combining accent. Normalise text from users before comparing, hashing or counting it. Finally, 300 seeded cross-checks: += and join produce identical strings, the copy formula matches a brute-force prefix-by-prefix sum, and normalising to NFC gives the same result whatever form the text arrived in:

ok = True
for seed in range(300):
    rng = random.Random(seed)
    pieces = ["".join(rng.choice("abé") for _ in range(rng.randint(0, 5)))
              for _ in range(rng.randint(0, 30))]
    out = ""
    for p in pieces:
        out += p
    ok &= out == "".join(pieces)
    lengths = [len(p) for p in pieces]
    brute = sum(sum(lengths[: k + 1]) for k in range(len(lengths)))   # prefix by prefix
    ok &= copies_concat(pieces) == brute and copies_join(pieces) == len(out)
    word = "".join(rng.choice("aeioú") for _ in range(rng.randint(0, 8)))
    nfd = unicodedata.normalize("NFD", word)
    ok &= unicodedata.normalize("NFC", nfd) == unicodedata.normalize("NFC", word)
print(ok)                                                 # True

The complexity

• Index s[i], len(s): O(1).
• Slice s[i:j]: O(j - i), a copy.
• a + b: O(len(a) + len(b)), a new string.
• += in a loop: O(n²) in general; often faster in CPython, never guaranteed.
• "".join(parts): O(total length).
• Substring search x in s: linear on typical inputs; the exact worst case depends on the interpreter's algorithm.

The Python cheat sheet has join versus += next to the list costs.

Where it goes wrong

• Expecting a method to edit in place. s.strip() alone changes nothing.
• Building output with += in a hot loop. Use a list and join, or io.StringIO.
• Recursing on slices. Pass start and end indexes instead of s[1:].
• Comparing unnormalised Unicode. Equal-looking strings differ; normalise first.
• Joining non-strings. "".join([1, 2]) raises TypeError; convert with map(str, ...).

When it shows up in interviews

Under almost every string problem: reversing words, string compression, valid palindrome and encode and decode strings all depend on building output efficiently and not slicing in a loop. Interviewers often ask "what is the complexity of your string building?" precisely to see whether you know += copies. In languages such as Java and C# the same advice is phrased as "use a StringBuilder", and as of October 2026 that rule holds across mainstream languages with immutable strings.

How to say it in an interview

"Python strings are immutable, so every operation that looks like an edit builds a new string. That makes them safe to share and hash, but repeated += in a loop can copy everything built so far each time, which is O(n²). CPython sometimes optimises that in place, but it is not guaranteed, so I collect pieces in a list and join once, which is linear. I also avoid slicing inside loops or recursion, since each slice is a copy, and I normalise Unicode before comparing user text."