Two patterns that solve half of string interviews
Because a string indexes in O(1) like an array, two techniques cover an enormous number of string problems.
Pattern 1: two pointers. Keep two indexes, usually one at each end, and walk them toward each other. One pass, O(n), no extra memory. Classic use: checking whether a string is a palindrome (reads the same backward, like "racecar").
Pattern 2: frequency counting. Walk the string once and tally each character in a dict. Then answer questions from the tallies instead of re-scanning. Classic use: anagrams (same letters, different order, like "listen" and "silent").
Start with two pointers:
Code exercise · python
Run this palindrome check. `left` and `right` start at the two ends and walk inward. The moment two mirrored characters differ, the answer is False. At most n⁄2 comparisons: O(n).
Quiz
In the two-pointer palindrome check, why can the loop stop when `left >= right`?
Code exercise · python
Your turn: anagrams by counting. Implement `char_counts(s)` returning a dict of character tallies (use `counts.get(ch, 0) + 1`), then `is_anagram(a, b)` that compares the two count dicts with ==. Two strings are anagrams exactly when their tallies match.
Why counting beats sorting here
Another correct anagram check is sorted(a) == sorted(b): same letters sort into the same sequence. It works, but sorting costs O(n log n) (you will prove that in Algorithms), while one counting pass is O(n).
The deeper lesson generalizes far beyond strings: a scan question can often become a lookup question. "Do these two things contain the same items?" becomes "do their tally dicts match?". You used a dict for O(1) lookups in lesson 1-1, and unit 6 opens up how dicts pull that off.
Space matters too: the counting dict holds at most one entry per distinct character, so its extra memory is O(k) for k distinct characters, tiny for text.
Problem
A function checks anagram-ness with sorted(a) == sorted(b). Another uses character-count dicts. For very long strings, which one does fewer steps: "sorting" or "counting"?