String Patterns: Two Pointers and Counting

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:

The two-pointer palindrome check

left and right start at the two ends and walk inward, comparing mirrored characters.

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

for word in ["racecar", "level", "python", "noon", "data"]:
    print(word, is_palindrome(word))

Output

racecar True
level True
python False
noon True
data False

The moment two mirrored characters differ, the function returns False without examining the rest, which is why python costs one comparison and noon costs two.

At most n⁄2 comparisons happen before the pointers meet, so the whole check is O(n). Just as importantly it uses no extra memory, since the two indexes are the only storage beyond the string itself.

Both odd and even lengths work without a special case. In racecar the pointers land on the middle e and the loop condition ends things, because a lone middle character has no partner to disagree with.

The loop can stop when left >= right because every pair beyond that point has already been compared from the other side.

Comparing s[left] with s[right] checks a mirrored pair, so the pair (2, 5) and the pair (5, 2) are the same check. Once the pointers meet or cross, every pair has been examined exactly once, and continuing would only repeat work in reverse.

The case where they land on the same index is the odd-length one, where a lone middle character has no partner and needs no check.

That single inward pass is what makes the routine O(n) rather than O(n²). A naive version comparing the string against its reverse also works, but it builds a whole new string first, spending O(n) memory to save nothing.

Anagrams by counting

The second pattern: tally every character, then compare tallies instead of re-scanning.

def char_counts(s):
    counts = {}
    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1
    return counts

def is_anagram(a, b):
    return char_counts(a) == char_counts(b)

print(is_anagram("listen", "silent"))
print(is_anagram("stressed", "desserts"))
print(is_anagram("python", "typhoon"))

Output

True
True
False

counts.get(ch, 0) reads the current tally and defaults to 0 the first time a character appears, which avoids a separate check for whether the key exists yet.

is_anagram is then a single line, because == on two dicts compares keys and values rather than identity. Two strings are anagrams exactly when their tallies match, so the comparison is the whole algorithm.

The third case shows why counts and not just letter sets are needed. typhoon and python use nearly the same letters, but typhoon has two o characters against one, so the tallies differ and the answer is False.

Why counting beats sorting here

Another correct anagram check is sorted(a) == sorted(b), since the same letters sort into the same sequence. It works, and it is shorter, but sorting costs O(n log n), a fact the Algorithms course proves, while one counting pass is O(n).

The deeper lesson generalizes well past strings: a scan question can often become a lookup question. Do these two things contain the same items becomes do their tally dicts match, which replaces repeated searching with a single pass plus a comparison.

You already relied on that substitution in lesson 1-1, where a dict turned 10,000 checks into one, and unit 6 opens up how dicts manage it.

Space is worth accounting for too. The counting dict holds at most one entry per distinct character, so the extra memory is O(k) for k distinct characters, which is tiny for ordinary text and never approaches the length of the string.

Counting does fewer steps on very long strings.

Building the two tally dicts is one O(n) pass over each string, where sorting both costs O(n log n). At n = 1,000,000 that is roughly 2 million steps against something closer to 40 million.

Both approaches are correct, and for short strings the sorting version is a perfectly reasonable choice given how little code it takes. The difference is purely in how each one responds to growth, since the log n factor multiplies rather than adds.