Immutability and construction costs

Understand the idea

Python strings are immutable. Each transformed result is a new value. Repeatedly copying a growing prefix can make construction quadratic; collect fragments and join once instead.

Work through an example

Joining ['learn','then','solve'] with spaces produces 'learn then solve'. Repeated copies of lengths 1,2,…,n total Θ(n²) characters.

Time and space complexity

Join O(total output length) time/output; do not rely on concatenation optimizations.

Why it works

Fragments retain their intended order until final assembly.

Common mistakes

• s[0]='x' is invalid.
• String slices generally allocate new strings.

Chapter lab · Python implementation

These examples operate on Python Unicode code points. A user-visible character can span several code points; normalization and grapheme segmentation need separate policies. The lab compares mirror positions without allocating a reversed copy. For every text problem, state whether case, punctuation, and whitespace matter.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

def palindrome(text):
    left, right = 0, len(text)-1
    while left < right:
        if text[left] != text[right]:
            return False
        left += 1
        right -= 1
    return True

def frequencies(text):
    counts = {}
    for char in text:
        counts[char] = counts.get(char,0)+1
    return counts

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert palindrome('level') and palindrome('')
assert not palindrome('lever')
assert frequencies('abaca')=={'a':3,'b':1,'c':1}