Strings

Strings show up in a huge share of interview problems: anagrams, palindromes, parsing, sliding windows. Python strings are immutable, compactly stored objects. Knowing how they're stored tells you which operations are cheap, which copy, and why one innocent-looking loop can turn $O(n)$ code into $O(n^2)$.

How CPython stores a string#

Immutable. Once created, a str never changes. s.upper(), s.replace(...) and s + t all return a new string. Immutability is what makes strings safe to share between functions and usable as dict keys.

Fixed width per string (PEP 393). CPython picks the smallest width that fits the widest character in that string, and uses it for every character:

So appending one emoji to 1,000 ASCII characters gives a new string of about 4,000 data bytes, not 1,004. The pay-off is $O(1)$ indexing: with uniform width, s[i] is just start + i * width. Mixed widths would force a scan from the start.

Length and hash are stored. len(s) reads a stored size field, so it's $O(1)$. The hash is computed the first time it's needed (for example, the first dict lookup) and cached in the object, so later lookups with the same string object skip rehashing.

Interning. CPython keeps one shared copy of some strings, mainly identifier-like literals ("hello_world") and names used in code. That lets the interpreter compare names by address. You can force it with sys.intern(s). It is an optimisation, not a guarantee, so compare strings with ==, never is.

What operations cost#

Here is what common string operations cost for a string of length $n$:

The += trap and the join fix#

Since strings can't grow, result += ch builds a brand-new string and copies everything so far into it, every iteration. Building a string of length $n$ that way copies about $n^2/2$ characters.

"".join(parts) scans the parts once to compute the total length, allocates once, then copies each piece straight into place: $O(n)$.

words = ["a"] * 5

# Slow pattern: new string each iteration
result = ""
for w in words:
    result += w

# Fast pattern: collect in a list, join once
parts = []
for w in words:
    parts.append(w)        # amortised O(1)
fast = "".join(parts)

print(result == fast)      # True

Quick check#

Test yourself on the ideas above.

Method reference#

Case conversion#

Searching#

Checking (return bool)#

Trimming#

Splitting and joining#

Replacing and padding#

Partitioning#

Interview idioms#

These one-liners come up again and again in string problems.

from collections import Counter

s = "listen"
print("".join(sorted(s)))   # 'eilnst': anagram signature
print(s[::-1])              # 'netsil': reversed copy
print(ord("c") - ord("a"))  # 2: char -> 0..25 index for count arrays
print(chr(ord("a") + 3))    # 'd': index -> char
print(Counter(s)["l"])      # 1: character frequencies
chars = list(s)             # mutable copy for in-place style edits
chars[0] = "L"
print("".join(chars))       # 'Listen'

Gotchas#

Watch out for these common string mistakes.

• Every "modifying" method returns a new string. s.strip() on its own line does nothing useful; write s = s.strip().
• find vs index: find returns -1 when absent, index raises. Watch for if s.find(x):, which is falsy when the match is at index 0.
• split() vs split(" "): bare split() collapses runs of whitespace and drops leading/trailing space. "a b".split() → ["a","b"], but "a b".split(" ") → ["a","","b"].
• Slices copy. In a loop, s[i:] costs $O(n)$ each time. Pass indices to recursive helpers instead of slicing.
• String hashes vary between runs (hash randomisation), so never rely on hash(s) being stable across processes.

Key takeaways#

• Strings are immutable; every change makes a new object.
• Each string uses 1, 2 or 4 bytes per char depending on its widest char, which keeps indexing $O(1)$.
• len is $O(1)$, slicing and concatenation copy, and the hash is cached after first use.
• Build strings with a list and "".join, not += in a loop.
• Compare strings with ==; interning is an implementation detail.