18 MIN GUIDE · INTERMEDIATE · STRINGS

Strings: Frequencies, Matching and Palindromes

Choose representations for characters, build linear-time pattern matching, and reason about substrings, subsequences and palindromes.

A string is an indexed sequence

Most array techniques also apply to strings, but character encoding and immutability matter. Indexing is cheap; repeatedly concatenating inside a loop may not be. Build pieces in a list or buffer when the output grows one character at a time.

Always distinguish these terms:

A substring is contiguous.
A subsequence preserves order but may skip characters.
A prefix starts at index 0; a suffix ends at the last index.
An anagram preserves every character frequency but not order.

Frequency signatures

A frequency map is the safest general signature. A fixed array of 26 counts is faster only when the input is guaranteed to contain lowercase English letters. Sorting gives a simple canonical form in O(k log k); counting takes O(k).

A set records presence, not multiplicity. It cannot distinguish abb from ab.

Matching without restarting

Naive pattern matching restarts after every mismatch and may take O(nm). KMP preprocesses the pattern into lps[i]: the length of the longest proper prefix of pattern[0..i] that is also a suffix. A mismatch falls back through this table while the text index keeps moving forward, so matching is O(n + m).

Rolling hash is useful for comparing many fixed-length windows, but equal hashes must still be verified when collisions are unacceptable.

Palindromes

Every palindrome has an odd centre on a character or an even centre between characters. Expanding from all 2n−1 centres finds the longest palindromic substring in O(n²) time and O(1) extra space. Dynamic programming is useful when a problem asks about many palindromic intervals; Manacher's algorithm is the specialist linear-time extension.

Frequency example

from collections import Counter
print(str(Counter("listen") == Counter("silent")).lower())

Output

true

Choosing a pattern

Use frequency counting for anagrams, two pointers for comparison from both ends, a sliding window for the best substring satisfying a constraint, KMP or Z for exact pattern matching, and trie traversal when many strings share prefixes.

Practice Valid Anagram, Find a Pattern with KMP, and Longest Palindromic Substring in increasing difficulty.