Sliding Window on String

Find All Anagrams

Slide a window of size len(pattern) across the string. Compare the window's character frequency with the pattern's frequency. If they match, the window position is an anagram occurrence.

O(n)

O(1)

How It Works

To find every anagram of a pattern P inside text S, slide a fixed-size window of length |P| across S and compare character frequencies. Initialize counts for the first window, then on each slide decrement the outgoing character and increment the incoming one — an O(1) update. Whenever the window's frequency profile equals P's, the window start is a match.

Re-counting each window from scratch would cost O(n·m); the incremental update brings it to O(n) with a 26-way comparison, or O(n) exactly if you maintain a 'matched characters' counter instead of comparing full arrays. This fixed-window variant differs from longest-substring problems, where the window size varies.

Step-by-Step Visualization

Find all anagrams of 'abc' in string

Window [0..2]

Windowcba

Anagram?Yes! → index 0

1/4

Code

Java

static List<Integer> findAnagrams(String s, String p) {
  List<Integer> result = new ArrayList<>();
  int[] pCount = new int[26];
  int[] sCount = new int[26];

  for (char c : p.toCharArray()) pCount[c - 'a']++;
  for (int i = 0; i < s.length(); i++) {
    sCount[s.charAt(i) - 'a']++;
    if (i >= p.length()) sCount[s.charAt(i - p.length()) - 'a']--;
    if (Arrays.equals(sCount, pCount)) result.add(i - p.length() + 1);
  }
  return result;
}

Tips & Gotchas

1Use a fixed-size sliding window equal to pattern length

2Compare character frequency maps of window and pattern

3Use a matches counter to avoid comparing full maps each step

Practice Problems

1Find All Anagrams in a String
2Permutation in String
3Substring with Concatenation of All Words

About the Sliding Window on String Pattern

Apply the sliding window technique to strings. Use a frequency map inside the window to track character counts. Expand or shrink the window based on whether the current set of characters satisfies the problem's condition.

Key insight

Think of strings as arrays of characters. Frequency maps solve most comparison problems. For substring search, know KMP or rolling hash to beat O(n·m).

Common String Interview Problems

Longest Substring Without Repeating Characters
Valid Anagram
Longest Palindromic Substring
Minimum Window Substring
Group Anagrams

Frequently Asked Questions

How is this different from the variable-size sliding window?

Here the window size is locked to the pattern's length, so both pointers move together in lockstep. Variable windows grow and shrink based on a validity condition, which suits longest or shortest substring questions instead of exact-size matching.

Comparing two int[26] arrays each slide feels expensive — can I avoid it?

Maintain a counter of how many of the 26 letters currently have matching counts between window and pattern. Each slide changes at most two letters, so you update the counter in O(1) and declare a match when it reaches 26.