Arrays, Strings, and Pattern Techniques · Pattern Techniques

Sliding Window

Sliding windows maintain information about a contiguous segment while expanding and shrinking the segment efficiently.

Enroll Now Text Us Contact Code Scholars Full DSA Course

Student Focus

This is taught as a reusable pattern for strings, arrays, and introductory competitive programming.

Guided Lesson Notes

Understanding Sliding Window

Sliding window is a pattern for contiguous ranges in arrays and strings. Instead of rebuilding the answer for every possible subarray, the algorithm keeps one active window and updates a small amount of state as the window moves.

The reason this works is reuse. When the right edge moves forward by one item, the old window is almost the same as the new window. For a fixed-size window, one item enters and one item leaves. For a variable-size window, the right edge expands until the window becomes invalid, then the left edge shrinks until the invariant is restored.

The invariant is the heart of the pattern. In a maximum-sum length-k problem, the invariant might be: currentSum is exactly the sum of the last k elements. In a longest-substring problem, the invariant might be: every character count inside the current window stays within the allowed limit.

Sliding window is not a magic replacement for all nested loops. It usually needs a monotonic condition: after the right side expands, moving the left side forward should help repair the window. That is why nonnegative array sums work naturally, but arrays with negative numbers often need prefix sums, hash maps, or a deque instead.

Competitive programming problems often hide sliding window behind phrases like longest contiguous block, shortest subarray, at most k, no more than k distinct values, or every window of length k. The winning move is to define what enters, what leaves, and what state must be updated in O(1).

Visual Model

A small picture for Sliding Window

i=0

i=1

i=2

i=3

i=4

i=5

Window

left = 1, right = 3, values [1, 5, 1]

State

current sum = 7, best length = 3

Invariant

The active window sum stays at most the limit.

Key Ideas

Fixed-size windows
Variable-size windows
Maintaining counts or sums

Practice Prompts

Find the maximum sum of any length-k subarray.
Find the longest substring that satisfies a character constraint.

Vocabulary

Terms students should be able to say clearly

Window

The contiguous section from left to right that is currently being considered.

Left pointer

The start of the current window; it moves forward when the window must shrink.

Right pointer

The end of the current window; it moves forward to include new items.

Window state

The sum, count map, frequency array, or other summary of the current window.

Fixed-size window

A window that keeps the same length, such as every subarray of length k.

Variable-size window

A window that expands and shrinks to satisfy a condition.

Worked Example

Worked example: longest sum-at-most window

For nums = [2, 1, 5, 1, 3, 2] and limit = 7, find the longest contiguous segment whose sum is at most 7.

1Start with left = 0, sum = 0, best = 0. The window is empty.
2Add 2 and 1. The window [2, 1] has sum 3, so best becomes 2.
3Add 5. The window [2, 1, 5] has sum 8, which is too large. Move left past 2, leaving [1, 5] with sum 6.
4Add 1. The window [1, 5, 1] has sum 7, so best becomes 3.
5Add 3. The sum becomes 10. Move left past 1 and 5 until the window [1, 3] has sum 4.
6Add 2. The window [1, 3, 2] has sum 6. The best length stays 3.

Complexity Check

Costs students should be able to explain

Operation	Typical Cost	Reason
Move right pointer	O(n) total	The right pointer visits each index once.
Move left pointer	O(n) total	The left pointer also only moves forward, never backward.
Maintain counts or sum	O(1) per move	Each enter or leave event updates a small state variable or map entry.

Common Mistakes

What to watch while practicing

Recomputing the full window sum after every movement instead of updating it incrementally.
Moving the left pointer only once when the window may still violate the condition.
Using sliding window when negative numbers break the monotonic shrink behavior.
Updating the best answer before restoring the window invariant.

Interview-Style Coding Problem

Sliding Window interview problem: Longest Repeating Character Window

Interview medium

Problem

Given an uppercase string s and an integer k, return the length of the longest substring that can be made of one repeated character after changing at most k characters.

Input

The first line contains s. The second line contains k.

Output

Print the maximum valid window length.

Sample Input

AABABBA
1

Sample Output

Why the sample works

A window such as AABA can be changed into AAAA with one replacement, so the best length is 4.

Approach

1Maintain a left and right pointer over the string.
2Track the most frequent character count inside the current window.
3If window length minus that count is greater than k, shrink from the left.
4The largest window that survives the rule is the answer.

O(n) time and O(1) extra space.

Java Solution

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.nextLine().trim();
    int k = Integer.parseInt(sc.nextLine().trim());

    int[] freq = new int[26];
    int left = 0;
    int maxFreq = 0;
    int best = 0;

    for (int right = 0; right < s.length(); right++) {
      int add = s.charAt(right) - 'A';
      freq[add]++;
      maxFreq = Math.max(maxFreq, freq[add]);

      while (right - left + 1 - maxFreq > k) {
        freq[s.charAt(left) - 'A']--;
        left++;
      }

      best = Math.max(best, right - left + 1);
    }

    System.out.println(best);
  }
}

Python Solution

s = input().strip()
k = int(input())

freq = [0] * 26
left = 0
max_freq = 0
best = 0

for right, ch in enumerate(s):
    idx = ord(ch) - ord('A')
    freq[idx] += 1
    max_freq = max(max_freq, freq[idx])

    while right - left + 1 - max_freq > k:
        freq[ord(s[left]) - ord('A')] -= 1
        left += 1

    best = max(best, right - left + 1)

print(best)

Practice Challenge

Make the idea your own

Write the variable-size template from memory: expand right, update state, shrink left while invalid, then update the answer only when the invariant is true.

Tutoring Connection

Turn the topic into usable problem-solving skill

Students can use this page before a lesson, after a difficult homework assignment, or while preparing for AP Computer Science A extensions, Advanced Topics in CS, USACO growth, or a college data structures course.

Schedule Free Consultation Text Us Open Online Compiler