Strings: operations & patterns

String problems dominate interview banks because they exercise everything at once: iteration, hashing, two-pointer technique, and one subtle performance trap that trips up almost everyone — immutability.

Why this matters

Because a Python str cannot be changed in place, "appending" to a string actually allocates a brand-new string and copies all existing characters. Do that in a loop and an innocent-looking solution silently becomes O(n²). The lesson is linearized: we start from the single most important fact (immutability and the join-vs-concat consequence), then the everyday methods, then the character-arithmetic trick (ord(c) - ord('a')) that powers frequency arrays, then translate/maketrans and slicing tricks, then formatting — finishing with four compact, fully worked interview patterns.

The one big idea

Strings are immutable. To build a string in a loop, accumulate the pieces in a list and ''.join them once at the end — O(n) total — rather than s += x each iteration, which is O(n²). Internalize this and most string-perf bugs disappear.

Immutability — why ''.join is O(n) but += in a loop is O(n²)

A str object's characters cannot change. s += c creates a new string of length len(s)+1 and copies the old contents in. Repeat n times and you copy 1 + 2 + ... + n ≈ n²/2 characters total — O(n²). The fix: collect pieces in a list (append is O(1)) and join once — O(n).

chars = ["a", "b", "c", "d"]

# SLOW PATTERN (shown for contrast — correct result, bad complexity):
slow = ""
for c in chars:
    slow += c                                    # each += copies everything
assert slow == "abcd"

# FAST PATTERN — the one to actually write:
fast = "".join(chars)                            # single O(n) pass
assert fast == "abcd"

# join also inserts a separator between pieces.
assert ",".join(["x", "y", "z"]) == "x,y,z"
assert " ".join(str(n) for n in [1, 2, 3]) == "1 2 3"

Gotcha

s += c in a loop is the most common accidental O(n²) in interview code — it looks linear but every += copies the whole accumulated string. Always build a list and "".join() once. (CPython sometimes optimizes a tight += loop in place, but you cannot rely on it, and it never applies once the string escapes the loop.)

Common methods — split / strip / find / replace / case / predicates

Strings come with a rich method set, and none of them mutate — they all return new strings. split() with no argument splits on runs of whitespace; find returns -1 when absent while index raises; startswith/endswith accept a tuple of options.

# split / rsplit / splitlines
assert "a,b,c".split(",") == ["a", "b", "c"]
assert "  many   spaces ".split() == ["many", "spaces"]   # no-arg: runs of WS
assert "a-b-c".rsplit("-", 1) == ["a-b", "c"]             # split from the RIGHT
assert "l1\nl2\nl3".splitlines() == ["l1", "l2", "l3"]

# strip / lstrip / rstrip — trim whitespace (or any given chars).
assert "  hi  ".strip() == "hi"
assert "xxhixx".strip("x") == "hi"

# find vs index: find returns -1 if absent; index RAISES ValueError.
assert "hello".find("l") == 2
assert "hello".find("z") == -1
assert "hello".count("l") == 2

# replace (all occurrences by default; an optional count limits it).
assert "aaa".replace("a", "b") == "bbb"
assert "aaa".replace("a", "b", 2) == "bba"

# startswith / endswith — also accept a tuple of options.
assert "report.csv".endswith((".csv", ".tsv")) is True
assert "report.csv".startswith("rep") is True

# case methods.
assert "Hello".lower() == "hello" and "Hello".upper() == "HELLO"
assert "hello world".title() == "Hello World"
assert "Hello".swapcase() == "hELLO"

# predicates — classify content (all chars must qualify; empty str is False).
assert "abc".isalpha() is True
assert "123".isdigit() is True
assert "abc123".isalnum() is True
assert "abc1".isalpha() is False

ord / chr and the 26-letter array trick

ord(c) gives a character's Unicode code point; chr(n) is the inverse. For lowercase a–z, ord(c) - ord('a') maps 'a'→0 ... 'z'→25. That index lets you use a fixed-size list[26] as a frequency table — O(1) per char, no hashing overhead, and trivially comparable. This is the counting trick.

assert ord("a") == 97 and chr(97) == "a"
assert ord("A") == 65
# 'a'->0, 'z'->25.
assert ord("a") - ord("a") == 0
assert ord("z") - ord("a") == 25

# Caesar shift by 1 (wrap z->a), built with the index trick.
def shift1(ch):
    return chr((ord(ch) - ord("a") + 1) % 26 + ord("a"))
assert shift1("a") == "b" and shift1("z") == "a"

# ASCII is 0..127; Python str holds full Unicode, so one character can be
# far above 127. len() counts CODE POINTS, not bytes.
assert ord("☕") > 127
assert len("café") == 4                          # 4 characters (not bytes)

translate / maketrans — bulk character mapping in one C-level pass

str.maketrans builds a translation table; str.translate applies it. Use it to replace or delete many characters at once, faster and clearer than chained .replace() calls. The third argument of maketrans lists characters to delete.

# Map vowels to '*'.
table = str.maketrans("aeiou", "*****")
assert "education".translate(table) == "*d*c*t**n"

# Third arg of maketrans lists characters to DELETE.
strip_punct = str.maketrans("", "", ",.!?")
assert "a,b.c!".translate(strip_punct) == "abc"

Slicing for reversal & palindrome check

s[::-1] reverses a string in O(n). s == s[::-1] is the quick palindrome test — though the two-pointer version below avoids building a reversed copy.

assert "abcde"[::-1] == "edcba"
assert ("racecar" == "racecar"[::-1]) is True
assert ("hello" == "hello"[::-1]) is False

f-string formatting & zero-padding

Format specs live after a colon inside {}. The ones that show up most in interviews: :05d zero-pads to width 5; :>8 / :<8 / :^8 align right/left/center; :.2f sets decimal places; :b / :x give binary / hex; :, adds thousands separators.

assert f"{42:05d}" == "00042"                    # zero-pad to width 5
assert f"{7:>4}" == "   7"                        # right-align in width 4
assert f"{7:<4}" == "7   "                        # left-align
assert f"{7:^5}" == "  7  "                       # center
assert f"{3.14159:.2f}" == "3.14"                 # 2 decimals
assert f"{255:b}" == "11111111"                   # binary
assert f"{255:x}" == "ff"                         # hex
assert f"{1234567:,}" == "1,234,567"              # thousands separators

String interview patterns — four worked problems

Anagram check — same multiset of characters. The Counter approach is O(n) time and O(k) space (k distinct chars). Sorting both strings also works but is O(n log n).

from collections import Counter

def is_anagram(a, b):
    return Counter(a) == Counter(b)

Palindrome via two pointers converging from both ends — O(n) time, O(1) extra space, no reversed copy built. Prefer this over s == s[::-1] for huge strings, or when you must also skip non-alphanumerics or compare case-insensitively in the same scan.

def is_palindrome_two_pointer(s):
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True

Frequency array using the 26-letter index trick — O(n) time, O(1) space (the table is a fixed 26 ints). Two strings are anagrams iff their frequency arrays are equal, and comparing arrays is cheaper than hashing.

def char_frequency_array(s):
    counts = [0] * 26
    for ch in s:
        counts[ord(ch) - ord("a")] += 1          # O(1) indexed bump
    return counts

Run-length encoding — "aaabbc" → "a3b2c1". Build the pieces in a list and join once (the immutability rule), giving O(n) time and O(n) space for the output.

def run_length_encode(s):
    if not s:
        return ""
    parts = []                                   # accumulate, join later
    run_char = s[0]
    run_len = 1
    for ch in s[1:]:
        if ch == run_char:
            run_len += 1
        else:
            parts.append(f"{run_char}{run_len}")  # flush the finished run
            run_char = ch
            run_len = 1
    parts.append(f"{run_char}{run_len}")          # flush the final run
    return "".join(parts)                         # single O(n) build

Complexity

Anagram by Counter or frequency array is O(n); by sorting it is O(n log n). Two-pointer palindrome is O(n) time and O(1) space, beating s == s[::-1] which allocates a full reversed copy. RLE is O(n) only because it joins once — the same algorithm with += would be O(n²).

Each pattern is exercised with assertions, including the edge cases that interviewers probe — the empty string is a palindrome, a single character RLE-encodes to "x1", and the empty string encodes to "".

assert is_anagram("listen", "silent") is True
assert is_anagram("abc", "abd") is False

assert is_palindrome_two_pointer("racecar") is True
assert is_palindrome_two_pointer("abca") is False
assert is_palindrome_two_pointer("") is True     # empty is a palindrome

assert char_frequency_array("listen") == char_frequency_array("silent")

assert run_length_encode("aaabbc") == "a3b2c1"
assert run_length_encode("x") == "x1"
assert run_length_encode("") == ""

Self-check

Every routine in this lesson is asserted in the runnable source. The one rule that carries the whole lesson: strings are immutable, so build with a list and "".join() once — and the rest is method fluency plus the ord(c) - ord('a') counting trick.