String Operations & Immutability

Jr Codex DSA Notes

Level: Beginner–Intermediate Prerequisites: Chapter 4 Time to complete: ~20 minutes

Table of Contents

1. Strings Are Immutable Sequences
2. The Cost of Concatenation in a Loop
3. The Fix: Build a List, Join Once
4. Common String Methods for DSA Problems
5. Strings as Arrays
6. Summary & Next Steps

1. Strings Are Immutable Sequences

You met this in Python Notes Module 1, Chapter 4 — worth restating here because it directly drives a common DSA performance trap. A string can't be changed in place; every "modification" actually creates a brand-new string:

name = "cat"
name[0] = "b"        # TypeError — strings don't support item assignment
 
name = "b" + name[1:]    # this WORKS — but it's a new string object, not a mutation

2. The Cost of Concatenation in a Loop

Because every += on a string builds an entirely new string, doing it repeatedly inside a loop is far more expensive than it looks:

def build_string_slow(chars):
    result = ""
    for char in chars:
        result += char        # each += may copy the ENTIRE string built so far
    return result
    # Looks like O(n), but can behave like O(n²): the 1st concat copies 1 char,
    # the 2nd copies 2, the 3rd copies 3, ... total copying ≈ 1+2+...+n = O(n²)

This is the exact same shape as the "hidden nested cost" trap from Module 1, Chapter 6 (the items[1:] slicing example) — an operation inside a loop that looks O(1) is actually O(k), and it compounds across the whole loop.

3. The Fix: Build a List, Join Once

Lists support O(1) amortized appends (Chapter 1), so accumulate pieces in a list and join them into a string exactly once at the end:

def build_string_fast(chars):
    pieces = []
    for char in chars:
        pieces.append(char)     # O(1) amortized each time
    return "".join(pieces)       # O(n) once, at the end
    # O(n) total — no repeated copying

Rule of thumb: if you're concatenating strings inside a loop, that's a signal to build a list instead and .join() at the end.

4. Common String Methods for DSA Problems

None of these are free — each one that appears inside another loop multiplies into your total complexity, exactly as in Module 1, Chapter 3's "function calls inside loops" rule.

5. Strings as Arrays

For algorithmic purposes, a string behaves like an array of characters — indexing, slicing, and iteration all work the same way arrays do (Chapter 1), just without in-place mutation:

word = "hello"
 
word[0]        # 'h'       — O(1) index access
word[1:4]      # 'ell'      — O(k) slice, builds a new string
list(word)     # ['h','e','l','l','o']  — convert to a mutable list when you need in-place edits
"".join(list(word))    # back to a string when you're done

This "convert to a list, mutate, join back" pattern is exactly what Chapter 6's in-place string reversal uses, since two-pointer swapping requires mutability that a raw string doesn't offer.

6. Summary & Next Steps

Key Takeaways

• Strings are immutable — every modification produces a new string object.
• Concatenating with += inside a loop can silently degrade from O(n) to O(n²) because each concatenation may copy everything built so far.
• The fix is to accumulate pieces in a list (O(1) amortized appends) and "".join() once at the end.
• When a problem needs in-place character mutation, convert the string to a list, mutate it, then "".join() back.

Concept Check

1. Why does result += char inside a loop risk O(n²) behavior instead of O(n)?
2. What's the fix, and why does it avoid the repeated-copying problem?
3. Why can't two-pointer swapping (Chapter 3) be applied directly to a Python string?

Next Chapter

→ Chapter 6: Pattern-Based String Problems

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index