Fixed Windows With Frequency Counts

Some windows never change width

The previous reading allowed left to move only when the current region needed repair or minimization. A fixed-size window has a predetermined width. Every time the right edge moves forward after the first full window, the left edge moves forward as well.

Suppose you need the maximum sum of any three consecutive values:

[4, 2, 1, 7, 8, 1, 2]
 └───┘

The first window sums to 4 + 2 + 1 = 7. The next window does not need a fresh three-value sum. Remove the outgoing 4 and add the incoming 7:

next sum = 7 - 4 + 7 = 10

function maxSumOfThree(nums: number[]): number | null {
  if (nums.length < 3) return null

  let sum = nums[0] + nums[1] + nums[2]
  let best = sum

  for (let right = 3; right < nums.length; right += 1) {
    sum += nums[right]
    sum -= nums[right - 3]
    best = Math.max(best, sum)
  }

  return best
}

The outgoing index is right - windowSize. After adding index right, that is the value immediately before the new window’s left boundary.

Permutation in String: Compare Character Frequencies

Two strings are permutations when they contain the same characters with the same frequencies. For example:

"abc" and "bca" → same inventory
"abc" and "abb" → different inventory

To determine whether a longer text contains a permutation of a pattern, every candidate substring must have the same length as the pattern. That gives us a fixed window size.

For lowercase English letters, represent the inventory with 26 counters:

index 0 stores the count of a
index 1 stores the count of b
...
index 25 stores the count of z

function letterIndex(character: string): number {
  return character.charCodeAt(0) - "a".charCodeAt(0)
}

function sameCounts(left: number[], right: number[]): boolean {
  for (let i = 0; i < 26; i += 1) {
    if (left[i] !== right[i]) return false
  }
  return true
}

Checking 26 positions is constant work because the alphabet size does not grow with the input. The important condition is that the problem explicitly limits characters to this alphabet.

Maintain Pattern and Window Frequency Counts

One count array describes the pattern and one describes the current text window. Expand the right edge one character at a time. Once the window would exceed the pattern length, remove the character that just fell outside its left edge.

function containsPermutation(pattern: string, text: string): boolean {
  if (pattern.length > text.length) return false

  const needed = new Array<number>(26).fill(0)
  const window = new Array<number>(26).fill(0)

  for (const character of pattern) {
    needed[letterIndex(character)] += 1
  }

  for (let right = 0; right < text.length; right += 1) {
    window[letterIndex(text[right])] += 1

    if (right >= pattern.length) {
      const outgoing = text[right - pattern.length]
      window[letterIndex(outgoing)] -= 1
    }

    if (right >= pattern.length - 1 && sameCounts(needed, window)) {
      return true
    }
  }

  return false
}

The comparison begins only after the first complete window exists. Before that point, the window is shorter than the pattern and cannot be its permutation.

Worked trace: pattern "ab", text "eidbaooo"

window  counts of relevant letters  match?
ei      e:1, i:1                   no
id      i:1, d:1                   no
db      d:1, b:1                   no
ba      b:1, a:1                   yes

When moving from db to ba, remove the outgoing d and add the incoming a. The frequency arrays now match even though ba and ab have different order.

The invariant after each complete-window update is:

window contains exactly the character frequencies from text[right - pattern.length + 1] through text[right].

That statement explains both the outgoing index and the position of the matching window.

Find All Anagrams: Record Every Matching Window

Find All Anagrams in a String uses the same window and the same invariant. The only change is what happens on a match: record the current window’s left boundary instead of returning.

function findAnagrams(text: string, pattern: string): number[] {
  if (pattern.length > text.length) return []

  const needed = new Array<number>(26).fill(0)
  const window = new Array<number>(26).fill(0)
  const starts: number[] = []

  for (const character of pattern) needed[letterIndex(character)] += 1

  for (let right = 0; right < text.length; right += 1) {
    window[letterIndex(text[right])] += 1

    if (right >= pattern.length) {
      window[letterIndex(text[right - pattern.length])] -= 1
    }

    if (right >= pattern.length - 1 && sameCounts(needed, window)) {
      starts.push(right - pattern.length + 1)
    }
  }

  return starts
}

For text "cbaebabacd" and pattern "abc", the matching windows begin at indices 0 and 6: "cba" and "bac" contain the required inventory.

Optional Optimization: Track How Many Character Counts Match

Instead of comparing all 26 counters after every movement, you can maintain how many letter positions currently match between the two arrays. Updating the incoming and outgoing letters changes only a few positions.

That optimization reduces the constant factor but introduces delicate update ordering. The straightforward comparison is already O(26n), which simplifies to O(n) for a fixed alphabet. Start with the version whose invariant you can explain correctly. Optimize only when the constraints or interviewer require it.

Complexity and boundaries

Each text character enters and leaves the window once. Comparing the fixed 26-element arrays takes constant work, so total time is O(n + m), where n is the text length and m is the pattern length. The two count arrays use O(26), or O(1), auxiliary space.

For a large or unrestricted character set, 26 is no longer a valid constant. Use Maps and track only observed characters, then describe complexity in terms of the number of distinct characters.