What Python string operations cost

Strings and tries Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
parts = []
for i in range(4):
    parts.append(str(i))
s = "-".join(parts)
print(s, len(s), s[::-1])

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 0-1-2-3 7 3-2-1-0

Right: join places the separator between items only.

join copies each piece once into a string of known size, which is why it beats repeated concatenation.

Why not the others?
  • B 0-1-2-3- 8 -3-2-1-0. join does not add a trailing separator.
  • C 0123 4 3210. The separator here is '-'.

30-second answer

Strings are immutable: slicing s[i:j] copies j - i characters, s + t builds a new string, and s += c in a loop can cost O(n²) in general (CPython sometimes optimises it, but do not rely on it). Indexing and len() are O(1). Build with a list and "".join(), and pass indexes instead of slices into recursive helpers.

Practise saying it · 30 s. No recording, just a timer

Explain string costs in Python.

Say your answer out loud, then check which of these points you covered:

  • Immutable
  • Slices copy
  • Build with join

Deep dive

s[::-1] is O(n); fine once, costly inside a loop.

in on strings searches substrings; on sets it is a hash lookup.

Comparing two strings is O(length) in the worst case.

Common mistakes

  • Slicing in a loop that runs n times, turning O(n) into O(n²).
  • Counting on += being fast in every Python implementation.

Senior take & follow-ups

Mention join and index passing; both are concrete, visible improvements.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you check a string reads the same backwards in O(1) memory?

    Show hint

    Two indexes moving inward, comparing characters.

  2. Why pass indexes to recursive helpers?

    Show hint

    Slices copy; indexes do not, so each call is O(1) to set up.

What each operation costs: Trie · KMP Algorithm · Rabin Karp · String Matching

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.