Strings and String Algorithms

Build the mental model

Python strings are immutable: once created, a string object's characters can never be changed in place. This means every `+=` on a string doesn't extend the existing object — it allocates a brand-new string large enough for the combined result and copies both the old content and the addition into it. That's harmless once, but inside a loop it compounds badly: on iteration k, the accumulated string is already roughly length k, so each `+=` copies about k characters, and summing that copying cost across n iterations (1 + 2 + 3 + ... + n) totals roughly n²/2 character copies — O(n²) overall, even though it looks like an innocent O(n) loop. The fix is to never accumulate strings incrementally. Instead, collect the pieces in a list — appending to a list is amortized O(1), as covered earlier — and call "".join(pieces) once at the end. join knows the total length up front (by scanning the list once), allocates exactly one final string of the right size, and copies each piece into it exactly once, for a true O(n) total cost. The rule of thumb: build with a list, join once.

Connect it to a real scenario

When the Tutorial Platform renders a lesson page, it's assembling one HTML string out of many pieces — the title, each code block, each paragraph, the exercise, the pitfalls list. Doing that assembly with repeated string += across a lesson with hundreds of fragments would quietly become O(n²) and slow page generation as lessons get longer; collecting every fragment into a list first and calling "".join() once keeps rendering O(n) no matter how many fragments a lesson has, which is exactly the pattern real template engines use under the hood.

Python strings are immutable — every += creates a brand-new string and copies both operands into it
Repeated += concatenation in a loop is O(n²) total, because each iteration copies a growing amount of already-accumulated text
Collecting pieces in a list and calling "".join() once is the correct O(n) pattern

Try the working example

python

words = ['Data', 'Structures', 'and', 'Algorithms', 'are', 'fun']

# Slow pattern: repeated += creates a new string and copies everything each time -> O(n^2)
result_slow = ''
for word in words:
    result_slow += word + ' '

# Fast pattern: collect pieces, join once -> O(n) total
result_fast = ' '.join(words)

print('Slow result:', result_slow.strip())
print('Fast result:', result_fast)
print('Equal content:', result_slow.strip() == result_fast)

You should see

Prints the same sentence built two ways ('Data Structures and Algorithms are fun') and confirms they're equal in content, even though the += version does far more copying under the hood as more words are added.

5-minute try-it

Write a timing comparison: build a sentence from a list of 50,000 words using the += pattern versus the join pattern, and print how many times slower += is.

One important caution

Using += concatenation inside a loop because it 'looks fine' on small test data (a handful of words), not noticing the O(n²) blowup until the input reaches thousands of pieces in production.

Calling "".join() on a list that still contains non-string items (numbers, None) — join requires every element to already be a str, so this raises a TypeError unless you explicitly convert each item first, e.g. "".join(str(x) for x in items).

Python Docs — Text Sequence Type str — Data Structures & Algorithms