LeetCode 567 · Medium · Sliding Window

Permutation in String

Given two lowercase strings s1 and s2, return true if some rearrangement of s1 appears in s2 as a contiguous block, and false otherwise.

O(n)time · n = s2.length()
O(26)space
matches = 26fixed-size window

lowercase a–z · s1: 1–8 letters · s2: 1–20 letters

c1 vs c2 per letter: needed by s1 (c1) and inside the window (c2) · green = equal and used · blue = differs · matches counts equal slots, zeros included

public boolean checkInclusion(String s1, String s2) { if (s1.length() > s2.length()) { return false; } int[] c1 = new int[26]; int[] c2 = new int[26]; for (int i = 0; i < s1.length(); i++) { c1[s1.charAt(i) - 'a']++; c2[s2.charAt(i) - 'a']++; } int matches = 0; for (int i = 0; i < 26; i++) { if (c1[i] == c2[i]) { matches++; } } int l = 0; for (int r = s1.length(); r < s2.length(); r++) { if (matches == 26) { return true; } int i = s2.charAt(r) - 'a'; // letter entering c2[i]++; if (c1[i] == c2[i]) { matches++; } else if (c1[i] + 1 == c2[i]) { matches--; } i = s2.charAt(l) - 'a'; // letter leaving c2[i]--; if (c1[i] == c2[i]) { matches++; } else if (c1[i] - 1 == c2[i]) { matches--; } l++; } return matches == 26;}
l
—
r
—
window
—
matches
—

Why it works

  1. Brute force sorts every window of length s1.length() and compares it with sorted s1: O(n · m log m). Recounting each window from scratch is O(n · m).
  2. A permutation has the same letter counts. Slide a window of exactly s1.length() across s2: one letter enters on the right, one leaves on the left, so only two counts change per step.
  3. Track agreement, not counts. matches is how many of the 26 letters have c1 == c2. Each change can only flip one slot between equal and not equal, so matches updates in O(1), and 26 means the window is a permutation.
  4. Why O(n): one O(26) setup, then O(1) work per window position. Space is two arrays of 26.
  5. Pitfall: the loop checks matches before sliding, so the last window is only checked by the final return matches == 26. Forget that line and a match at the very end is missed.