Strings — the most underestimated DSA topic

Two facts about Python strings change how you write string code, and both trip up beginners.

Fact one — strings are immutable. Every operation that 'modifies' a string creates a new one. result += 'x' in a loop creates n new strings, each one bigger than the last, total work O(n²). For long strings or many concatenations, this is brutal.

The fix is one of the most-cited Python idioms. Build a list, join at the end:

parts = []
for x in items:
    parts.append(transform(x))
result = ''.join(parts)

List append is O(1) amortised. join() does one pass over the list. Total: O(n). Identical output, much better complexity.

Fact two — strings are sequences of code points, not bytes. len('café') is 4, not 5. Iterating gives you four characters, even though the UTF-8 encoding is 5 bytes (because é is two bytes in UTF-8).

This is correct behaviour for almost every text operation you care about (word counts, slicing, indexing). It's confusing only when you're working at the byte level — networking, hashing, certain low-level file formats. For those cases, .encode('utf-8') gives you a bytes object, which IS indexed by byte.

Most of the bugs around code points happen at boundaries — Python strings vs bytes for files, strings vs bytes for network protocols, strings vs bytes for MD5 hashing. Always know which you're holding.

For everyday string work — slicing, searching, splitting, joining — Python's str does the right thing. Treat strings like immutable arrays of characters. Build with join(). Avoid += in loops. Reach for the byte representation only when you really mean bytes.

A surprising number of string problems reduce to 'count the characters'. Once you know three patterns for character counting, half of string DSA falls.

Pattern one — collections.Counter. Counter(s) returns a dict-like mapping character to count. Two strings are anagrams if and only if Counter(a) == Counter(b). Cleanest possible solution. O(n) time. O(k) space where k is the alphabet size.

from collections import Counter
is_anagram = Counter(a) == Counter(b)

Pattern two — sorting. sorted(a) == sorted(b) also tests anagram, because two anagrams have the same characters in different orders, and sorting normalises both to the same string. O(n log n) time, slightly more memory. The code is one line. Use when n is small or you need to sort anyway.

Pattern three — frequency array. For ASCII strings, an array of size 128 (or 26 for lowercase letters) with counts is faster than a dict. Increment for one string; decrement for the other; check that all entries are zero. C-style and fast. Used inside performance-critical string libraries.

Which to use? Start with Counter. It reads the cleanest, works on Unicode, and is fast enough for almost all practical inputs. Switch to sorting if it's a one-line solution. Switch to a frequency array only if you've measured Counter as a bottleneck and the alphabet is fixed (ASCII or smaller).

The broader pattern. Many 'is X an anagram/permutation/rearrangement of Y' problems reduce to character counting. Same with 'find all substrings that are anagrams', 'group anagrams together' — each variation builds on the same primitive.

Know the primitive. Apply it. Move on.

A leetcode classic, and a perfect example of the sliding-window pattern from yesterday.

The problem — given a string, find the length of the longest substring with no repeated characters.

Brute force enumerates every substring and checks each for uniqueness. That's O(n²) substrings, each O(n) to check, so O(n³) total. Painful past a few thousand characters.

Sliding window does it in O(n) time, O(k) space where k is the alphabet size.

Look at the snippet. We maintain a window defined by left and right indices, plus a dict mapping each character to its most recent index.

For each right (we walk the right edge forward through the string), we check if the current character is already in our window. 'In the window' means seen before, and its previous index is at or after left.

If yes, we shrink from the left — set left to one past the last occurrence. The window is now repeat-free.

In either case, update the character's last-seen index and track the maximum window length so far.

Key insight — we never go backward. Right only moves forward; left only moves forward (or stays). Each character enters the window once and leaves at most once. Total work O(n).

This pattern — left and right pointers, a hash structure tracking what's in the window, expand-from-right-shrink-from-left logic — solves almost every 'longest/shortest/best subarray with constraint X' problem. Variations include longest substring with at most k distinct characters, minimum window substring containing all characters of a target, longest repeating character replacement.

Memorise the shape. Variations are tweaks to the constraint-violation rule.

Pop quiz: what's the fastest way to remove all punctuation from a string in Python?

The answers people reach for:

A regex — re.sub(r'[^\w\s]', '', text). Works. But regex is overkill for character-level replacement, and it's slow for this use case.

A loop with replace() — for c in punctuation: text = text.replace(c, ''). Quadratic in the worst case (each replace scans the whole string). And reads ugly.

A list comprehension — ''.join(c for c in text if c not in punctuation). Better. But character-by-character iteration in pure Python isn't fast.

The answer most don't know — str.translate with str.maketrans:

import string
table = str.maketrans('', '', string.punctuation)
clean = text.translate(table)

str.maketrans('', '', chars) builds a translation table that deletes each character in chars. str.translate applies it in a single C loop. 10-100x faster than regex for character-level operations.

When this matters in real ML work — preprocessing tokens at scale. NLP pipelines normalise punctuation, strip control characters, transliterate accented characters. Every microsecond per token compounds across millions of tokens. translate() is dramatically faster than regex for these use cases.

When NOT to use translate — when you need patterns. 'Replace any sequence of digits with [NUM]' is a regex job. 'Match HTML tags' is a regex job. Anything pattern-shaped, regex.

For character-level swaps, deletions, or transliterations — translate. For pattern-level work — regex. Two tools, different jobs.

The Python world has moved on from 'regex everything' for a few years now. The standard library has better-suited tools for character-level work; learn them.

End of Day 17. Strings are the most-used and most-underestimated structure in DSA. They're also the bread and butter of any ML/data role — tokenisers, log parsing, normalisation, embeddings, all string-heavy.

What we covered.

Morning, the two facts that change how you write string code. Strings are immutable; build with join(), not +=. Strings are code points, not bytes; len('café') is 4, not 5. Both are correctness issues as much as performance issues.

Midday, the three patterns for character counting that solve most string DSA. Counter (default), sorted compare (one-liner), frequency array (when speed truly matters). Anagram, permutation, character histogram problems all build on these.

Afternoon, the longest-substring-without-repeats problem solved with a sliding window in O(n). The shape — left, right, hash structure of what's in the window — generalises to many 'best subrange with constraint' problems.

Evening, str.translate as the right tool for character-level transformations. 10-100x faster than regex. Reach for regex only when you actually need patterns.

A larger theme. Most string DSA problems are 'apply a primitive (counter, slice, sort, window) to a transformation of the input'. Once you have the primitives, the problems are recognising which primitive applies.

Tomorrow, Day 18, linked lists. Less relevant in real ML work than other structures, but a fixture in interviews and a great test of pointer-manipulation skill. Reverse a linked list, detect a cycle, merge sorted lists — the canonical exercises.

See you in the morning.