Every place an anagram begins

def anagram_starts(s, p):
    k = len(p)
    need = [0] * 26                  # count in p minus count in the window
    for c in p:
        need[ord(c) - 97] += 1
    off = sum(1 for x in need if x)  # letters whose counts still differ

    def bump(c, d):
        nonlocal off
        i = ord(c) - 97
        if need[i] == 0:
            off += 1
        need[i] += d
        if need[i] == 0:
            off -= 1

    out = []
    for hi, c in enumerate(s):
        bump(c, -1)                  # c enters the window
        if hi >= k:
            bump(s[hi - k], +1)      # the letter k places back leaves
        if hi >= k - 1 and off == 0:
            out.append(hi - k + 1)
    return out

#include <string>
#include <vector>
#include <array>

std::vector<int> solve(const std::string& s, const std::string& p) {
    int k = (int)p.size();
    std::array<int, 26> need{};                    // count in p minus count in the window
    for (char c : p) need[c - 'a']++;
    int off = 0;
    for (int x : need) off += x != 0;              // letters whose counts still differ
    auto bump = [&](char c, int d) {
        int& x = need[c - 'a'];
        if (x == 0) ++off;
        x += d;
        if (x == 0) --off;
    };
    std::vector<int> out;
    for (int hi = 0; hi < (int)s.size(); ++hi) {
        bump(s[hi], -1);                           // enters
        if (hi >= k) bump(s[hi - k], +1);          // leaves
        if (hi >= k - 1 && off == 0) out.push_back(hi - k + 1);
    }
    return out;
}

import java.util.*;

class Solution {
    public List<Integer> anagramStarts(String s, String p) {
        int k = p.length();
        int[] need = new int[26];                  // count in p minus count in the window
        for (char c : p.toCharArray()) need[c - 'a']++;
        int off = 0;
        for (int x : need) if (x != 0) off++;      // letters whose counts still differ
        List<Integer> out = new ArrayList<>();
        for (int hi = 0; hi < s.length(); hi++) {
            int i = s.charAt(hi) - 'a';            // enters
            if (need[i] == 0) off++;
            if (--need[i] == 0) off--;
            if (hi >= k) {                         // leaves
                int j = s.charAt(hi - k) - 'a';
                if (need[j] == 0) off++;
                if (++need[j] == 0) off--;
            }
            if (hi >= k - 1 && off == 0) out.add(hi - k + 1);
        }
        return out;
    }
}

function anagramStarts(s, p) {
  const k = p.length, need = new Array(26).fill(0);   // count in p minus count in the window
  for (const c of p) need[c.charCodeAt(0) - 97]++;
  let off = need.filter(x => x !== 0).length;         // letters whose counts still differ
  const bump = (c, d) => {
    const i = c.charCodeAt(0) - 97;
    if (need[i] === 0) off++;
    need[i] += d;
    if (need[i] === 0) off--;
  };
  const out = [];
  for (let hi = 0; hi < s.length; hi++) {
    bump(s[hi], -1);                                  // enters
    if (hi >= k) bump(s[hi - k], +1);                 // leaves
    if (hi >= k - 1 && off === 0) out.push(hi - k + 1);
  }
  return out;
}

fn solve(s: &str, p: &str) -> Vec<usize> {
    let (s, p) = (s.as_bytes(), p.as_bytes());
    let k = p.len();
    let mut need = [0i32; 26];                     // count in p minus count in the window
    for &c in p { need[(c - b'a') as usize] += 1; }
    let mut off = need.iter().filter(|&&x| x != 0).count() as i32;
    let mut bump = |need: &mut [i32; 26], c: u8, d: i32| {
        let x = &mut need[(c - b'a') as usize];
        if *x == 0 { off += 1; }
        *x += d;
        if *x == 0 { off -= 1; }
        off
    };
    let mut out = Vec::new();
    for hi in 0..s.len() {
        let mut o = bump(&mut need, s[hi], -1);             // enters
        if hi >= k { o = bump(&mut need, s[hi - k], 1); }   // leaves
        if hi + 1 >= k && o == 0 { out.push(hi + 1 - k); }
    }
    out
}

import qualified Data.Map.Strict as M

-- Fold over the letters, each paired with the letter leaving the window (if any), carrying
-- need: pattern count minus window count, with zeros removed. The window is an anagram
-- exactly when the map is empty.
solve :: String -> String -> [Int]
solve s p = reverse found
  where
    k = length p
    start = M.fromListWith (+) [(c, 1) | c <- p]
    bump d c = M.alter (\x -> let v = maybe 0 id x + d in if v == 0 then Nothing else Just v) c
    leaving = replicate k Nothing ++ map Just s
    (_, found) = foldl step (start, []) (zip3 [0 ..] s leaving)
    step (m, acc) (hi, c, out) =
      let m' = maybe id (bump 1) out (bump (-1) c m)
          acc' = if hi >= k - 1 && M.null m' then (hi - k + 1) : acc else acc
      in (m', acc')