String and Scan

What is this?

There is no exotic algorithm here — you just walk through a string or array one time, from start to finish, while carrying along one small piece of information as you go. Maybe it is a running sum, a count, or the best value you have seen so far. The careful part is naming that one quantity precisely and knowing the exact moment to read it off; do that and the answer appears in a single pass.

💡 Fun fact: Best Time to Buy and Sell Stock is one of the most-asked warm-up questions at big tech companies, yet the trick is almost embarrassingly simple — just remember the cheapest price seen so far. The challenge is resisting the urge to write a slow nested-loop solution.

🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: a huge class of array and string problems needs nothing more than one left-to-right pass while you carry a small running quantity — a length difference, an accumulated shift, a count, or a best-so-far. The answer falls out as you scan; there is no second loop and no extra structure.

The pattern

Each problem walks the input once and maintains a single piece of state that you update at every position. The art is naming that state precisely and knowing exactly when to read it off.

• Single-pass case analysis. When comparing two strings, split on their lengths first, then walk once and allow exactly one mismatch — the case structure does the work that brute force would do with nested loops.
• Suffix or prefix accumulation. When each position is affected by everything after (or before) it, sweep from that end and carry a running sum, so each element's final value is computed in O(1).
• Count per run. When neighbors of the same kind form runs, the answer for each run depends only on its length; tally contributions run by run as you scan.
• Track best-so-far. When you want the optimal pair under an ordering constraint, remember the best left-hand value seen so far and test each new element against it.

The common thread: one variable, one pass, updated at every step.

The problems

One Edit Distance — two strings are one edit apart only if their lengths differ by at most one. Branch on the length case, then scan once: at the first mismatch, either skip one character (insert/delete) or step both (replace) and require the rest to match.

Shifting Letters — each shift applies to a prefix, so the total shift on a position is the sum of all shifts from there onward. Sweep right to left accumulating a running suffix sum, and apply it to each character with a modulo-26 wrap.

Remove Colored Pieces if Both Neighbors are the Same Color — a run of k identical colors yields k - 2 valid moves for that player. Scan, measure each run, and tally each player's moves; compare the totals to decide the winner.

Best Time to Buy and Sell Stock — track the minimum price seen so far; at each day, the best profit is the price minus that running minimum. Keep the best profit across the single pass.

Key takeaways

1. Many sequence problems need just one linear pass and one running variable.
2. Name your state precisely — length case, suffix sum, run length, or best-so-far — and update it every step.
3. Suffix and prefix sums turn "depends on everything after me" into O(1) per element.
4. Track a min or best-so-far to solve ordered-pair optimizations without nested loops.
5. The instinct to build here — sweep once, carry a little state — underpins sliding windows and prefix-sum chapters later.