Merge / compare two strings in lockstep

32 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Is abc a subsequence of ahbgdc? A subsequence keeps the letters in order but may skip letters in between. By hand you would look for an a in the long string, then look for a b after it, then a c after that. Easy.

The careless version of this is slow: for each letter of abc, search the long string from the beginning, or try every way of choosing three positions out of six, which is 20 ways here and billions for long strings. The careful version only ever moves forward, and that is the pattern.

Build the structure, one piece at a time

Two pointers, one per string. i points at the next unmatched letter of the short string s; j points at the next unread letter of the long string t. The rule is simple: compare s[i] with t[j]. On a match, advance both. On a mismatch, advance only j. Stop when either pointer runs off its end.

i reached 3, the length of s, so every letter was found in order: true. The same lockstep shape, with a different rule at each step, handles many two-string tasks: merging abc and pqr alternately into apbqcr takes one letter from each in turn and then appends whatever is left over; the longest common prefix of two strings advances both pointers while the letters agree and stops at the first difference.

Why it is correct

The invariant: s[0..i−1] is a subsequence of t[0..j−1], and i is the largest value for which that is true. Matching greedily, as early as possible, is safe: if s[i] can be matched at position j and also at some later position, choosing j leaves more of t available for the remaining letters, so it can never hurt. Therefore if any way of embedding s in t exists, the greedy scan finds one, and if the scan ends with i short of the end, no embedding exists. For merging and prefix problems the invariant is the simpler "both pointers sit at the next unused letter of their string", which each step preserves by construction.

earliest match for s[i] leaves the longest suffix of t for s[i+1..]

Why it is fast

Each step advances at least one pointer, and neither pointer ever moves backwards, so there are at most n + m steps for strings of length n and m: O(n + m) time and O(1) memory. Restarting the search from the beginning for each letter would be O(n · m), and enumerating positions is exponential.

How to recognise it in an interview

Cues: two strings or two arrays, "in order", "subsequence", "merge", "common prefix", "compare". Say: I will walk both with one pointer each, never moving backwards, and decide at each step which pointer moves. Is Subsequence is the example. Merge Strings Alternately moves both pointers every step and copies the leftover tail. Backspace String Compare walks both strings from the end, skipping the characters that backspaces delete, and compares what survives.

02The idea in one line

Advance pointers through both strings together; handle leftovers.

Reach for it when: Merge strings alternately, is subsequence, longest common prefix, backspace compare.

Cost: O(n + m) time.

03The walk-through, step by step

The video works one example: Is Subsequence 'abc' in 'ahbgdc'. These are its captions in order, so you can follow without the video or check a step you missed.

1. Two pointers in lockstep: j always moves, i moves only on a match
2. t[0] = 'a' matches s[0]: advance both
3. t[1] = 'h' ≠ s[1]: skip it, advance j only
4. t[2] = 'b' matches s[1]: advance both
5. t[3] = 'g' ≠ s[2]: skip it, advance j only
6. t[4] = 'd' ≠ s[2]: skip it, advance j only
7. t[5] = 'c' matches s[2]: advance both
8. i reached the end of s: every character was found in order → true
9. Each pointer only moves forward: O(n + m) time, O(1) space

04Asked at Google

7 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in String Algorithms: KMP failure function, Rolling hash (Rabin–Karp), Reverse-and-build string transforms, Parse with a state machine, Multi-pattern scan with a set of lengths.