Strings: Problem Patterns

Array and String Patterns · 35 min

DSA · Strings

The same four patterns, over and over

Stage 0 taught you string syntax. This module is about recognition: palindromes converge two pointers inward, anagrams count characters, the longest palindromic substring grows outward from a centre, and atoi is one careful left-to-right scan. You will trace Top spot! by hand, then step both pointer walks yourself.

Walk the pointers through Top spot! →
Top spot!9 characters · one capital, a space, an exclamation mark
→
L →   ← Rcompare, skip, step inward · two integers of memory
→
palindrome3 comparisons · 2 skips · O(n) time, O(1) space

01 The idea

Recognise the shape, then write the loop

String questions in placement rounds look endless. Palindrome, anagram, compression, atoi, longest common prefix, longest palindromic substring — a new one every round. They are not endless. Almost all of them are one of four shapes, and the shape is decided by a single question: how does the index move?

Two indices starting at the ends and walking towards each other handles palindromes and in-place reversal. One index plus a small table of counts handles anagrams and character frequency. A centre that grows outward in both directions handles the longest palindromic substring. And one left-to-right scan carrying a little state — a sign, a running number, a run length — handles atoi and run-length compression. Naming the shape is most of the work. The loop that follows is four to seven lines.

Ask how the index moves. Two ends walking inward, one index with a table of counts, a centre growing outward, or one careful left-to-right scan — nearly every string question is one of those four.
Two-pointer convergeleft starts at index 0, right at the last index, and the loop runs while left < right. Each pass either compares the two characters or moves one pointer past something that should be ignored.
Frequency countA table from character to how many times it appears. Two strings are anagrams when their tables match — the order the characters were written in never enters the comparison.
Expand around centrePick a position, then step outward one character at a time while both sides still match. A string of length n has 2n − 1 centres, because a palindrome can sit on a character or in the gap between two.

02 Worked example

Is Top spot! a palindrome?

Nine characters — Top spot! — with one capital, one space, and one exclamation mark. A valid-palindrome check ignores every character that is not a letter or a digit, and compares letters without caring about case. left starts at index 0 and right at index 8. Every row below is one pass of the loop, and a pass does exactly one thing: skip a character, or compare a pair. The space is drawn as · so you can see it.

index012345678
L=0 R=8Top·spot!'!' is not a letter · R ← 7
L=0 R=7Top·spot!'T' lowercases to 't' = 't' · L ← 1 R ← 6
L=1 R=6Top·spot!'o' = 'o' · L ← 2 R ← 5
L=2 R=5Top·spot!'p' = 'p' · L ← 3 R ← 4
L=3 R=4Top·spot!the space is not a letter · L ← 4
L=4 R=4Top·spot!4 < 4 is false · the loop ends
resultTop·spot!palindrome · 3 comparisons, 2 skips
Count the comparisons: three, for nine characters. Not one character was copied, and the middle s was never compared with anything — a character always equals itself, so the loop stops the moment the pointers meet.

Two things did the real work. The pointers move inward, and a pointer is allowed to move on its own when the character under it does not count. That second rule is what handles punctuation and whitespace without a second pass and without a cleaned copy. Hold on to the direction — inward — because the console's second mode reverses it: the longest palindromic substring starts in the middle and grows outward.

03 The code

Two patterns, four versions

First the palindrome, in the version most people write and the version interviewers want. Both are O(n) time, so the difference is memory — and, on a string that fails early, how much of it you read at all. Then the anagram check, where the difference is time and the honest answer is not the one-liner.

Naive · clean, copy, reverse

clean = ''for ch in s:    if isalnum(ch): clean += lower(ch)return clean == reverse(clean)   # O(n) extra memory

Two pointers · nothing copied

l = 0;  r = len(s) − 1while l < r:    if not isalnum(s[l]): l += 1; continue    if not isalnum(s[r]): r −= 1; continue    if lower(s[l]) != lower(s[r]): return false    l += 1;  r −= 1return true

Why two pointers when both are O(n) time? The naive version allocates a cleaned string and then a reversed one — up to 2n characters of new memory for a question that needs none. The two-pointer walk holds two integers, whatever the length of the input. "Can you do it in O(1) extra space?" is the standard follow-up, and this is the version that already answers it.

Why continue after moving one pointer? A skip is not a comparison. After l += 1 the loop condition has to be re-tested, because the new character might also be punctuation and because l might have reached r. On Top spot! that is exactly what happens at l = 3: the space pushes l to 4, l < r becomes false, and the loop ends without a fourth comparison. Drop the continue and you compare the space against a letter.

Why while l < r and not l <= r? When both pointers land on the same index there is nothing to compare, because a character always equals itself. On an odd-length palindrome that middle character is free. Using <= is not wrong in output, only wasteful — but it hides the fact that you know why the pointers may safely stop.

Now the second pattern, on characters from the same string. spot and stop are anagrams: same characters, different order. There are two standard answers, and the complexity gap between them is real.

By sorting · O(n log n)

if len(a) != len(b): return falsesa = sorted(a)      # 'spot' -> 'opst'sb = sorted(b)      # 'stop' -> 'opst'return sa == sb

By counting · O(n)

if len(a) != len(b): return falsecount = {}       # char -> count; a missing key reads as 0for ch in a: count[ch] += 1for ch in b:    count[ch] −= 1    if count[ch] < 0: return falsereturn true

Is counting actually faster, honestly? Yes, but say where it matters. Sorting is O(n log n) time and allocates two sorted copies; counting is O(n) time and O(k) space, where k is the alphabet size. On spot versus stop the difference is unmeasurable. On strings of 105 characters, or when you have to bucket 104 words, the log n factor is precisely what the question is testing.

Why the length check on line 1? Without it, counting att against at builds t: 2 and then decrements only one t. No count ever goes negative, so you return true for two strings that are not anagrams. The one-line check removes the entire class of bug, and it also lets the counting version exit early — with equal lengths, "no count went negative" is enough to prove every count landed back on zero.

Why one table and a decrement, rather than two tables compared? Same complexity, half the memory, and it can bail out on the first character that goes negative instead of finishing both strings. Comparing two hash maps is also easy to get wrong when one of them holds a key the other has never seen.

05 Cheat sheet

The family, and what each one costs

ProblemPatternCostThe trap
Valid palindromeTwo pointers convergingO(n) / O(1)Comparing after the pointers meet, and treating a skip as a comparison.
Anagram check, countingOne frequency tableO(n) / O(k)No length check first. Assuming 26 lowercase letters when the input can be anything.
Anagram check, sortingSort both, compareO(n log n) / O(n)Slower than counting, and it allocates two sorted copies — but the sorted string is the key you need to group anagrams.
Longest palindromic substringExpand around 2n − 1 centresO(n²) / O(1)Trying only odd centres, so abba comes back as a single character.
String to integer (atoi)One scan carrying stateO(n) / O(1)Checking overflow after the multiply. Not stopping at the first non-digit.
Longest common prefixVertical scan, column by columnO(total chars)Empty array, empty string, and running past the end of the shortest string.
Run-length compressionOne pass with a run counterO(n)Never flushing the final run. The output can be longer than the input.
Two integers, not two stringsWhenever you can answer using indices into the original string, you are at O(1) extra space. Building a cleaned copy is O(n) memory and it is the first thing you will be asked to remove.
k, not nA frequency table is O(k) space, where k is the alphabet size — 26 for lowercase English, 128 for ASCII, unbounded for Unicode. Say out loud which one you are assuming.
2n − 1 centresThe seven letters of topspot have 13 centres: 7 sitting on a character and 6 sitting in a gap. Missing the 6 gaps is the most common longest-palindromic-substring bug.

06 Where & why

Which pattern, and when not to

None of these four patterns is clever. Their value is that none of them needs a copy of the input — three of the four run in O(n) time, and the expansion is the one that does not — on questions most people first solve by building extra strings. And an interviewer can tell in about ten seconds which one you reached for.

Reach for a converging two-pointer when…

The answer depends on both ends at oncePalindrome, reverse in place, "two values in a sorted array that add to x". One left-to-right scan cannot see both ends of the data, and two indices are the cheapest way to fix that.
You have been given an O(1) space budgetThe walk holds two integers no matter how long the string is. Cleaning into a new string is O(n) memory and fails the constraint on the spot.
Some characters must be ignored in placeCase, punctuation, whitespace. A pointer that is allowed to move on its own does the filtering inside the same loop — no second pass, no second string.
The string is read once and thrown awayValidation, not indexing. If you will answer many questions about the same string, build a frequency table or a prefix array once instead of walking it repeatedly.

Use something else when…

SituationBetter choiceWhy
Many words must be grouped, not compared two at a timeSorted string as a hash-map keyChecking every pair is O(n²) anagram calls. Bucketing each word under its sorted form is one pass — this is the one job where sorting beats counting, because a sorted string is hashable as it stands.
You need the longest palindromic substring in linear timeManacher's algorithmExpand-around-centre is O(n²): each of the 2n − 1 centres can grow about n/2 times, so a thousand identical characters cost about half a million comparisons. Manacher reuses the radii it has already computed and runs in O(n).
You are searching for one string inside anotherKMP or Rabin–KarpConverging pointers say nothing about substring search. KMP's prefix function gives O(n + m) instead of the O(n·m) of restarting the match at every index.
Two strings differ by insertions, not just orderEdit-distance DPA frequency table carries no position information, so it cannot tell you how many edits apart two strings are — only whether they use the same characters.
The pattern is what is being checked, not the code. If you can say "this is a two-pointer converge, O(n) time and O(1) space" before you write a line, you have already answered the real question — and you will not sort a string in O(n log n) when counting it would have been linear.

07 Interview questions

What interviewers actually ask

Eleven questions in the order an interview escalates — the palindrome walk first, then the anagram trade-off, then centre expansion, then the parsing edge cases that decide the round.

How do you check whether a string is a palindrome, ignoring case and punctuation?
Two pointers converging. left at index 0, right at the last index, loop while left < right. If the character under a pointer is not a letter or a digit, move that pointer alone and re-test the condition; otherwise lowercase both and compare, and return false on the first mismatch. If the loop finishes, it is a palindrome. O(n) time, O(1) extra space.
Why two pointers instead of cleaning the string and comparing it with its reverse?
Both are O(n) time, so the difference is memory: the clean-and-reverse version allocates up to 2n new characters, and the walk holds two integers. It also short-circuits — on Race a car it returns false after four comparisons instead of building two full strings first. "Can you do it in O(1) extra space?" is the standard follow-up, and the walk is already the answer.
In that loop, why while l &lt; r and not while l &lt;= r?
When both pointers land on the same index there is nothing to compare — a character always equals itself. On Top spot! the loop ends with both pointers on the middle s, and that s is never compared with anything. <= gives the same answer but does one pointless comparison, and it suggests you have not thought about why stopping is safe.
Two ways to check anagrams — sorting or counting. Which do you pick?
Counting, and I say why. Sorting both strings is O(n log n) time plus two sorted copies; one frequency table and a decrement pass is O(n) time and O(k) space for an alphabet of size k. Sorting has exactly one real advantage: the sorted string is a hashable canonical key, which is what you need to group anagrams rather than compare two. spot and stop both sort to opst and both count to s:1 p:1 o:1 t:1.
Why does the counting version need a length check before it starts?
Because a leftover count is invisible to it. Counting att against at builds t: 2, then decrements one t and one a; nothing goes negative, so you return true for two strings that are not anagrams. With equal lengths, "no count went negative" is a proof that every count landed back on zero — that is why the one-line check is what makes the early exit valid.
Find the longest palindromic substring. What is your approach?
Expand around every centre. For each index, run the same expansion twice — once starting from (i, i) for odd lengths and once from (i, i+1) for even ones — stepping outward while the two characters match and the indices stay in range, and keep the widest span seen. That is O(n²) time and O(1) space. On the seven letters of topspot it does 13 comparisons and finds the whole string. If linear time is required, the answer is Manacher.
Why 2n − 1 centres and not n?
Because a palindrome can be centred on a character or in the gap between two. topspot is centred on the s, but abba is centred in the gap between the two bs — an odd-only loop returns a single character on it. n character centres plus n − 1 gaps is 2n − 1: 13 for 7 letters. Each centre can expand about n/2 times, which is where the O(n²) comes from.
Walk me through the edge cases of atoi.
Four, in order: skip leading whitespace; read an optional single + or -; read digits and stop at the first character that is not one, returning whatever you have; and clamp to the 32-bit signed range, −2147483648 to 2147483647. The clamp has to be tested before the multiply — once val * 10 has wrapped you cannot detect it — so check whether val > (2147483647 − d) / 10 first. " -042abc" returns −42: spaces skipped, sign read once, leading zeros harmless, parsing stops at a.
How do you find the longest common prefix of an array of strings?
Vertical scan. Compare character 0 of the first string against character 0 of every other string; if they all agree, move to character 1, and stop the moment one string is shorter than the current index or disagrees. That is O(total characters) worst case, O(1) extra space, and it exits early. On top, topspot, topaz it stops at index 3 because top has run out, and returns top. Handle the empty array and any empty string by returning the empty string.
Compress a string with run-length encoding. What is the trap?
The final run. The loop appends only when the character changes, and nothing changes after the last group, so it is silently dropped unless you flush it once the loop ends — that is the single most common bug in this question. The algorithm itself is one pass with a run counter: count how many times the current character repeats and, when it changes, append the character and its count. The second trap is that the output can be longer than the input: abc becomes a1b1c1, which is why many versions of the question ask you to return the original when compression does not shrink it. topppot becomes t1o1p3o1t1 — seven characters in, ten out.
Which of these would you actually use in production?
Almost none of them as written. Any standard library gives you reversed, sorted, a counter type, a strip function and a real integer parser, and a production palindrome or anagram check is one or two lines calling those. What survives is the pattern: converging pointers show up in two-sum on a sorted array, in reversing a buffer in place, and in every O(1) extra space constraint you will be handed. Interviews test the pattern because the pattern generalises — the specific string question does not.

08 Practice problems

Six problems, four patterns

Every one is solvable with what is above: converge, count, expand, scan. Name the pattern before you write the loop.

Reverse the letters only

Easy
Given a string, return it with its letters in reverse order but every character that is not a letter left exactly where it was. a1b!c becomes c1b!a.
Follow-up
Reversing the whole string would give c!b1a — the digits and punctuation have to stay at their original indices, so you cannot reverse first and patch up afterwards.
Show the hint
Two indices at the ends and the same skip rule as the palindrome walk. The difference is what happens when both pointers are finally sitting on letters.

Ransom note

Easy
Given a note and a page of magazine letters, return true if the note can be built by cutting characters out of the page, using each character on the page at most as many times as it appears there.
Follow-up
The two strings are not the same length, so the anagram argument does not carry over: here a surplus left over on the page is perfectly fine, and only a shortfall is fatal.
Show the hint
One table, one decrement pass — but decide before you write it which of the two strings gets counted and which gets decremented. Swapping them answers a different question.

Count palindromic substrings

Medium
Return how many substrings of s are palindromes. Substrings starting at different positions count separately even if they read the same, and every single character counts as one.
Follow-up
abba answers 6, not 1: a, b, b, a, bb and abba. Finding the longest and counting them all are not the same job.
Show the hint
The centre expansion needs no change at all — only the bookkeeping does. Ask what one successful outward step from a centre proves, and stop tracking a maximum.

Run-length decode

Medium
A run-length encoded string alternates a character with the number of times it repeats: t1o1p3o1t1 decodes to topppot. Given such a string, return the original.
Follow-up
A count is not always one digit — a12b3 means twelve as then three bs — so you cannot walk the string two characters at a time.
Show the hint
One left-to-right scan carrying two pieces of state: the character whose run you are reading, and the number built so far. Digits fold in with num = num * 10 + d; a non-digit is the signal to act.

Palindrome after one deletion

Medium
Return true if s can be turned into a palindrome by deleting at most one character. abca is true; abc is false.
Follow-up
You get exactly one deletion for the whole string, and at a mismatch it could be spent on either side — so one failed pair leaves you two candidates to test, not one.
Show the hint
Walk inward normally. Everything outside the first mismatch is already known to match, so the rest of the question is a plain palindrome check on a smaller range — write that check so it takes a range rather than a whole string.

Every anagram start index

Hard
Given a string s and a shorter string p, return every index in s at which a substring of length len(p) is an anagram of p. For s = cbaebabacd, p = abc the answer is [0, 6].
Follow-up
Building a fresh count table at every index is O(n · k), and that is precisely what the question is testing you not to do. When the window slides one place, only two characters change.
Show the hint
Keep one count table for the current window, plus a single number: how many distinct characters currently have the wrong count. Sliding by one touches at most two entries, so that number can only move a little.