Algorithms / Sliding Window Strings

Least You Need to Know: Two Pointers, Sliding Windows, and String Scans

Many interview string problems are not about deep string theory. They are about keeping a **contiguous window** consistent while scanning left to right. The key question is what summary of the current window lets you expand, shrink, and answer the prompt in overall linear time.

The least you need to know

A sliding window keeps a contiguous substring or subarray and updates it incrementally.
The right pointer usually expands the window; the left pointer shrinks it when an invariant is violated.
Linear-time window scans work because each pointer moves forward only, so each position is entered and left a bounded number of times.
A good window summary stores exactly what the constraint needs, such as counts, duplicates, or total sum.
Two pointers are useful when the problem asks about substrings, intervals, or maintaining a local condition during one pass.

Key notation

[L, R] current window from left index L to right index R

freq[c] count of character c inside the current window

invariant condition that the maintained window must satisfy

Tiny worked example

Suppose the task asks for the longest substring with no repeated characters.
Expand `R` one character at a time and update `freq`.
If a duplicate appears, move `L` rightward until the duplicate is removed.
After each repair step, the window again satisfies the invariant "all characters are unique," so its length is a valid candidate answer.

Common mistakes

Students often shrink the window only once even when the invariant is still broken.
Students sometimes recompute the whole window after every move instead of updating counts incrementally.
Students confuse a sliding window with arbitrary subsequences; the window must stay contiguous.

How to recognize this kind of problem

If the prompt asks for the longest or shortest substring satisfying a local condition, think sliding window.
If the state can be updated when one item enters and one item leaves, think window summary instead of nested loops.
If both pointers only need to move forward, a linear two-pointer design is often available.