Strings Basics
Python strings are sequences, much like lists, but with one rule that changes every complexity calculation you'll do around them: strings are immutable. Every operation that appears to "modify" a string — concatenation, replacement, uppercasing — actually builds and returns a brand new string object. That single fact is behind one of the most common accidental performance bugs in Python interview code.
Why Looping += Is O(n²)
Because strings can't be changed in place, result += next_char inside a loop allocates an entirely new string every single iteration and copies everything built so far into it. Building an n-character string this way does 1 + 2 + 3 + ... + n copy work, which sums to O(n²), not O(n).
# Looks O(n), actually O(n^2): every += allocates a new string and copies everything so far
def build_string_slow(chars):
result = ""
for c in chars:
result += c
return result
# Idiomatic fix: accumulate in a list (mutable, O(1) amortized append), join once at the end
def build_string_fast(chars):
parts = []
for c in chars:
parts.append(c)
return "".join(parts)
build_string_slow: Time complexity: O(n²) — the i-th iteration copies i
characters, and those copies sum to roughly n²/2. Space complexity: O(n) for the final string,
though many intermediate strings are allocated and discarded along the way.
build_string_fast: Time complexity: O(n) — each list append is amortized O(1), and
str.join() does one single-pass allocation and copy at the end. Space complexity: O(n) — the list of parts plus the final joined string.
Common String Operations and Their Complexity
| Operation | Complexity | Why |
|---|---|---|
| s[i] (indexing) | O(1) | Direct offset into the string's backing buffer. |
| s[a:b] (slicing) | O(b - a) | A brand new string is allocated and the selected characters are copied into it. |
| x in s | O(n · m) | Worst case for naive substring search on a haystack of length n and needle of length m (CPython's actual implementation is closer to this in the worst case, faster in typical cases). |
| s.find(x) | O(n · m) | Same substring-search cost as in, but returns an index instead of a bool. |
| s.split() | O(n) | One pass over the string, copying characters into new substrings. |
Worked Example: Palindrome Check — Slicing vs Two Pointers
The one-liner s == s[::-1] is genuinely idiomatic Python and perfectly fine to write in production code. But it's worth understanding what it costs, and why an interviewer might still ask you to write the two-pointer version by hand.
# Idiomatic and readable, but allocates a full reversed copy
def is_palindrome_slice(s):
return s == s[::-1]
# Two pointers: same answer, no extra string allocated
def is_palindrome_two_pointer(s):
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
is_palindrome_slice: Time complexity: O(n) — building the reversed copy visits every
character once, and the equality check is another O(n) pass. Space complexity: O(n) — the sliced
reversed string is a full new copy held in memory.
is_palindrome_two_pointer: Time complexity: O(n) — same order of growth, but with a
smaller constant (no reversed copy is built, and it can exit early on the first mismatch). Space complexity: O(1) — only two index variables, no new string allocated.