Reverse-and-build string transforms

29 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

Turn the sky is blue into blue is sky the: the words in reverse order, each word still spelled forwards. By hand you would read the words, write them on slips of paper, and lay the slips out backwards. That uses a second sheet the size of the first. Now suppose the sentence is stored in a fixed row of boxes, one letter per box, and you must do the job inside those boxes with no spare sheet, only a few pencil marks. Shuffling whole words around inside a row, each move shifting everything else along, is slow and easy to get wrong: moving one word of length w past the rest costs about n box copies, and there are many words.

Build the structure, one piece at a time

There is only one tool: reverse a stretch of boxes in place. Put one finger at each end of the stretch, swap the two letters, move both fingers inward, and repeat until they meet. For a stretch of w boxes that is w/2 swaps and no extra space.

Now use the tool twice.

1. Reverse the whole row: the sky is blue → eulb si yks eht. The words are now in the right order, but each one is spelled backwards.
2. Walk the row, find each word (a stretch between spaces), and reverse that stretch on its own:
   eulb → blue, giving blue si yks eht
si → is, giving blue is yks eht
yks → sky, giving blue is sky eht
eht → the, giving blue is sky the.

The result is blue is sky the: the original order the, sky, is, blue, read backwards. (The video's closing caption says "blue is the sky" as loose English; the exact reversed-order output is blue is sky the.) Many string problems are built from this one tool applied to chosen stretches: reverse the first k letters of every 2k block, rotate an array by d with three reversals, and so on.

Why it is correct

Reversing the whole row puts the words in reverse order, because the last box becomes the first: whatever was at the end of the row is now at the start, word by word, and each word's letters are reversed along with everything else. Reversing a single word's stretch flips its letters back without touching the boxes around it. Two reversals of the same stretch restore it exactly, so each word's spelling returns to the original while its new position is kept. Spaces are single boxes and stay where the first reversal put them, which is exactly between the reversed words.

reverse(w₁ w₂ … w_k) = rev(w_k) … rev(w₁), and rev(rev(w)) = w

Why it is fast

The whole-row reversal does n/2 swaps. The per-word reversals together touch every letter once more, another n/2 swaps at most. Total about n swaps: O(n) time with O(1) extra memory, two indices. Moving words one at a time inside the row costs O(n) per word and O(n²) overall. Building the answer on a second sheet is also O(n) but needs O(n) extra space, which is what in-place problems forbid.

How to recognise it in an interview

Cues: "in place", "O(1) extra space", "reverse words", "rotate", "every k characters", or a string transformation that is really a rearrangement of fixed chunks. Say: I will do it with in-place reversals of chosen stretches, usually the whole thing first and then the pieces. Reverse Words in a String is the example. Reverse String II reverses the first k letters of every block of 2k. Zigzag Conversion and Text Justification are the cousin form: build the output chunk by chunk into a buffer, one row or one line at a time.

02The idea in one line

Reverse in chunks, or build the answer backwards with a buffer.

Reach for it when: Reverse words, reverse words in place, zigzag, string compression, text justification.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: Reverse Words in 'the sky is blue'. These are its captions in order, so you can follow without the video or check a step you missed.

1. Two reversals: whole string first, then each word on its own
2. Reverse the whole string: words are in the right order but spelled backwards
3. Reverse 'eulb' → 'blue'
4. Reverse 'si' → 'is'
5. Reverse 'yks' → 'sky'
6. Reverse 'eht' → 'the'
7. Result: 'blue is the sky', built in place
8. Two linear passes, no extra buffer: O(n) 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), Parse with a state machine, Merge / compare two strings in lockstep, Multi-pattern scan with a set of lengths.