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.
جو کم از کم جاننا ضروری ہے
- 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.
اہم علامتیں
[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
مختصر حل شدہ مثال
- 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.
عام غلطیاں
- 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.
اس قسم کے سوال کو کیسے پہچانیں
- 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.
Next recommended lesson
Continue through this topic with Least You Need to Know: Sparse Tables, RMQ, and Static Idempotent Queries.
Least You Need to Know: Sparse Tables, RMQ, and Static Idempotent QueriesRelated lessons
Keep going with nearby lessons in the same topic.