beginnerintermediateadvanced

Algorithms · Strings

Strings

Palindromes, anagrams, pattern matching, and the Python tools built for text

Two pointerspalindrome check in O(1) space
Counts, not setsanagrams need frequency, not membership
ord(c) - ord('a')letter to 0-25 index
Substring vs subsequencecontiguous vs order-preserving

1.Palindrome checks

A palindrome reads the same forwards and backwards. Two pointers walking inward from both ends, comparing as they go, check this in O(n) without ever building a reversed copy.

Key features

s == s[::-1] is the short, pythonic version — it builds a reversed copy, O(n) time and space
The two-pointer version is also O(n) time, but O(1) extra space — no reversed copy is built
A real-world palindrome check ("A man, a plan...") first needs to strip case, spaces, and punctuation

Two pointers closing in from both ends check a palindrome in O(n) time, O(1) space — and a real sentence needs its case and punctuation stripped first.

2.Anagram checks (via sorting or frequency count)

Two strings are anagrams if they contain exactly the same characters, the same number of times each. Sorting both and comparing (O(n log n)), or comparing character counts with Counter (O(n)), both work — Counter is faster.

Key features

sorted(a) == sorted(b) is O(n log n) — simple, and correct if lengths differ (sorted lists of different lengths never compare equal)
Counter(a) == Counter(b) is O(n) — faster, and the more idiomatic Python approach
set(a) == set(b) is NOT an anagram check — sets discard how many times each character appears

Anagram checks need character COUNTS, not just which characters appear — Counter(a) == Counter(b) or sorted(a) == sorted(b), never set(a) == set(b).

3.Basic pattern matching (naive substring search)

The naive way to find a pattern inside text: try matching it starting at every possible position, comparing character by character, and stop at the first full match. O(n * m) worst case, where n is the text length and m the pattern length.

Key features

Try every starting position from 0 to n - m (inclusive) — a pattern cannot start any later and still fit
text[i:i+m] == pattern is a clean way to express "compare the pattern against text starting at i"
Worst case O(n * m) — real-world text rarely hits this, but a text of all one repeated character against a similar pattern does

A pattern of length m can start at any index from 0 to n - m INCLUSIVE — range(n - m + 1), not range(n - m).

4.`ord()` / `chr()` for character-to-index tricks

ord(c) gives a character's numeric code point; chr(n) does the reverse. ord(c) - ord('a') turns a lowercase letter into a 0-25 index — the trick behind fixed-size, 26-slot frequency arrays instead of a general dict.

Key features

ord(c) - ord('a') maps 'a'..'z' to 0..25 — a direct index into a 26-element array
chr(n) is the inverse: chr(ord("a") + i) recovers the i-th letter
This only works for ONE case — mixing uppercase and lowercase input breaks the arithmetic unless normalized first
A 26-slot list built this way is often faster and simpler than a dict when the alphabet is known and fixed

ord(c) - ord('a') maps a single case's letters to 0-25 — normalize case first with .lower()/.upper(), or mixed-case input silently produces out-of-range or negative indices.

5.Strings as immutable sequences (why in-place edits aren't free)

A Python string cannot be changed in place — s[0] = 'x' raises an error. Any 'edit' actually builds a brand-new string, which is why string-building patterns matter (§2's O(n²) `+=` trap comes directly from this).

Key features

s[i] = c raises TypeError — item assignment does not exist for strings
'Modifying' a string always means building a new one, e.g. s = 'b' + s[1:]
This is the root cause behind Big-O's `+=`-in-a-loop trap (§2) — immutability is WHY that pattern is O(n²)

A string can never be edited in place — every apparent edit builds an entirely new string, which is the root cause of §2's O(n²) `+=`-in-a-loop trap.

6.Building strings efficiently (join vs += in a loop)

Collect pieces in a list and call ''.join(pieces) once, rather than accumulating with += inside a loop — join is the practical fix; §2 covers exactly why += is O(n²).

Key features

''.join(pieces) is the standard, idiomatic fix for the += loop cost analyzed in §2
An f-string is the right tool for a single, one-off piece of formatted output — not for accumulating many pieces across a loop
join() works on any iterable of strings, not just a list — including a generator expression

Command

python

words = ["Data", "Structures", "and", "Algorithms"]
sentence = " ".join(words)

Collect pieces in a list and ''.join() once — never accumulate a string with += inside a loop.

7.Substring vs subsequence (distinction matters a lot)

A substring is a CONTIGUOUS run of characters from the original string. A subsequence keeps the original order but can skip characters — "ace" is a subsequence of "abcde" but not a substring of it.

Key features

Every substring is also a subsequence, but not every subsequence is a substring
in checks for a substring: "abc" in "xabcy" is True because those three letters are contiguous
Checking a subsequence needs its own logic — walking both strings and only advancing the pattern pointer on a match

A substring must be contiguous; a subsequence only needs to preserve order — every substring is a subsequence, but not the other way around.

8.Character frequency counting

Counting how many times each character appears in a string is the basis of anagram checks, first-unique-character problems, and more — a dict built manually does the job in O(n), and collections.Counter does the same thing in one call.

Key features

A manual frequency count is one pass, O(n), using dict.get(key, default) to handle first-time-seen characters
Counter(s) builds the identical mapping in one call, and adds extras like .most_common(n)
This same pattern (a dict counting occurrences) reappears constantly — anagrams, first unique character, majority element

Command

python

from collections import Counter

freq = Counter("banana")   # Counter({'a': 3, 'n': 2, 'b': 1})

A frequency count is one pass with dict.get(key, default) — Counter(s) is the same thing, already written, plus lookup helpers like .most_common(n).

9.`collections.Counter` for frequency maps

Counter(iterable) builds a dict-like frequency map in one call, and adds extras a plain dict does not have — most_common(n) for the top n items, and arithmetic operators for combining or subtracting counts.

Key features

Counter(iterable) counts occurrences of each element in one call
.most_common(n) returns the n most frequent items, as (item, count) tuples, highest first
Missing keys return 0 (not a KeyError) — Counter("cat")["z"] is 0
Two Counters support + and - directly, combining or subtracting their counts

Counter is a dict built for counting — reach for .most_common(n) instead of manually sorting a frequency dict by value.

10.`str.find()` vs manual scanning

str.find(pattern) does exactly what this section's naive_search does — returns the first matching index, or -1 — but as a C-implemented, highly optimized built-in. Write the manual version to learn the mechanism; use find() in real code.

Key features

str.find(pattern) returns the first matching index, or -1 if not found — same contract as a hand-written naive search
str.index(pattern) is nearly identical, but raises ValueError instead of returning -1
find() is implemented in C and highly optimized — it will outperform a hand-written Python loop on real workloads

Write a naive search once to understand the mechanism — then use str.find() (or str.index() when a missing match should raise) in real code.

Spotted a mistake on this page? Tell us.

Read Sheet