Strings — Anagrams, Palindromes, Substrings

Strings are arrays of characters with a fixed alphabet — usually small enough (ASCII 128, lowercase English 26) that you can use counting arrays instead of hash maps.

Anagrams

Two strings are anagrams iff they have the same character counts. Three solutions: (1) sort both and compare — $O(n \log n)$; (2) hash-map count of each char — $O(n)$ time, $O(\sigma)$ space where $\sigma$ is alphabet size; (3) for fixed small alphabets, a 26-int array is faster than a hash map by a constant factor.

Palindromes

A palindrome reads the same forward and backward. Check with two pointers from both ends, $O(n)$. To find the longest palindromic substring, expand around center: for each index, treat it as the center of an odd-length palindrome and try to expand; also try every adjacent pair as the center of an even-length one. $O(n^2)$ time, $O(1)$ space. Manacher's algorithm does it in $O(n)$ but is rarely worth the complexity.

Substring search

Naive substring search is $O(nm)$. KMP, Rabin-Karp, and Boyer-Moore all achieve $O(n + m)$ average. In practice, modern languages' built-in `find` / `indexOf` uses a tuned variant; rolling-hash (Rabin-Karp) is the easiest to code yourself and useful when you need to count multiple substrings.

Common interview problems

• Group anagrams: hash each string by its sorted form or by its 26-count tuple
• Longest substring without repeating chars: sliding window with a set
• Minimum window substring: sliding window with two character counts
• Valid palindrome (ignoring non-alphanumeric): two pointers with a skip rule