String problems are a favourite playground for algorithms: they look simple but demand an exact cost model. In this topic we normalize strings, check palindromes and anagrams, group anagrams and find the longest palindrome.
The cost model
In Python str is immutable. Every slice, lower(), replace() creates a new string costing O(n) time and memory. s[i] and len(s) cost O(1). sorted(s) returns a list of characters in O(n log n), and Counter counts in O(n). A hidden cost: s += c in a loop can sometimes be O(n^2) (see the next topic).
Normalization and the palindrome
A palindrome reads the same in both directions. In real text spaces, punctuation and case get in the way, so we normalize first: keep only letters and digits and lower-case them. Then t == t[::-1].
