567. Permutation string

567_solution1_two_maps.c

#include <stdbool.h>
#include <string.h>

// C has no hash map: a 128-slot array indexed by char stands in for one
static int freq[128], wfreq[128];
static int matches;

// change the window count of c by delta, keeping `matches` in sync
static void update(char c, int delta) {
    if (freq[(int)c] == 0)
        return; // not in s1: irrelevant
    if (wfreq[(int)c] == freq[(int)c])
        matches--; // was matching, about to change
    wfreq[(int)c] += delta;
    if (wfreq[(int)c] == freq[(int)c])
        matches++; // matches now
}

bool checkInclusion(char *s1, char *s2) {
    int k = strlen(s1), n = strlen(s2);
    memset(freq, 0, sizeof freq);
    memset(wfreq, 0, sizeof wfreq);

    int need = 0; // distinct letters in s1, fixed from here on
    for (int i = 0; i < k; i++)
        if (freq[(int)s1[i]]++ == 0)
            need++;
    matches = 0; // letters of s1 whose window count equals freq

    for (int right = 0; right < n; right++) {
        update(s2[right], +1); // char enters
        if (right >= k)
            update(s2[right - k], -1); // char leaves
        if (matches == need)
            return true;
    }
    return false;
}

567_solution2_diff_map.c

#include <stdbool.h>
#include <string.h>

// C has no hash map: a 128-slot array indexed by char stands in for one
static int diff[128];
static int mismatched;

// shift a letter's diff by delta, keeping `mismatched` in sync
static void update(char c, int delta) {
    if (diff[(int)c] == 0)
        mismatched++; // was balanced, about to break
    diff[(int)c] += delta;
    if (diff[(int)c] == 0)
        mismatched--; // now balanced again
}

bool checkInclusion(char *s1, char *s2) {
    int k = strlen(s1), n = strlen(s2);
    memset(diff, 0, sizeof diff);
    mismatched = 0;

    for (int i = 0; i < k; i++)
        update(s1[i], -1);

    for (int right = 0; right < n; right++) {
        update(s2[right], +1); // char enters
        if (right >= k)
            update(s2[right - k], -1); // char leaves
        if (mismatched == 0)
            return true;
    }
    return false;
}

567_solution3_two_arrays.c

#include <stdbool.h>
#include <string.h>

static int freq[26], wfreq[26];
static int matches;

// change the window count of a letter by delta, keeping `matches` in sync
static void update(char ch, int delta) {
    int c = ch - 'a';
    if (wfreq[c] == freq[c])
        matches--; // was matching, about to change
    wfreq[c] += delta;
    if (wfreq[c] == freq[c])
        matches++; // matches now
}

bool checkInclusion(char *s1, char *s2) {
    int k = strlen(s1), n = strlen(s2);
    memset(freq, 0, sizeof freq);
    memset(wfreq, 0, sizeof wfreq);
    for (int i = 0; i < k; i++)
        freq[s1[i] - 'a']++;

    // matches = number of the 26 letters whose window count equals freq
    matches = 0;
    for (int i = 0; i < 26; i++)
        if (freq[i] == wfreq[i])
            matches++; // empty window: letters absent from s1 already match

    for (int right = 0; right < n; right++) {
        update(s2[right], +1); // char enters
        if (right >= k)
            update(s2[right - k], -1); // char leaves
        if (matches == 26)
            return true;
    }
    return false;
}

567_solution1_two_maps.cpp

#include <string>
#include <unordered_map>
using namespace std;
class Solution {
public:
  bool checkInclusion(string s1, string s2) {
    int k = s1.size();
    unordered_map<char, int> freq, wfreq;
    for (char c : s1)
      freq[c]++;

    int need = freq.size();
    int matches = 0;

    auto update = [&](char c, int delta) {
      auto it = freq.find(c);
      if (it == freq.end())
        return;

      int target = it->second;
      if (wfreq[c] == target)
        matches--;

      wfreq[c] += delta;
      if (wfreq[c] == target)
        matches++;
    };

    for (int right = 0; right < s2.size(); right++) {
      update(s2[right], +1); // char enters

      if (right >= k)
        update(s2[right - k], -1); // char leaves

      if (matches == need)
        return true;
    }
    return false;
  }
};

567_solution2_diff_map.cpp

#include <string>
#include <unordered_map>
using namespace std;

class Solution {
public:
  bool checkInclusion(string s1, string s2) {
    int k = s1.size();
    unordered_map<char, int> diff;
    int mismatched = 0;

    auto update = [&](char c, int delta) {
      if (diff[c] == 0)
        mismatched++;
      diff[c] += delta;
      if (diff[c] == 0)
        mismatched--;
    };

    for (char c : s1)
      update(c, -1);

    for (int right = 0; right < s2.size(); right++) {
      update(s2[right], +1); // char enters
      if (right >= k)
        update(s2[right - k], -1); // char leaves
      if (mismatched == 0)
        return true;
    }
    return false;
  }
};

567_solution3_two_arrays.cpp

#include <array>
#include <string>
using namespace std;

class Solution {
public:
  bool checkInclusion(string s1, string s2) {
    int k = s1.size();
    array<int, 26> freq{}, wfreq{};

    for (char ch : s1)
      freq[ch - 'a']++;

    int matches = 0;
    for (int i = 0; i < 26; i++)
      if (freq[i] == wfreq[i])
        matches++; // empty window: letters absent from s1 already match

    auto update = [&](char ch, int delta) {
      int c = ch - 'a';
      if (wfreq[c] == freq[c])
        matches--;

      wfreq[c] += delta;
      if (wfreq[c] == freq[c])
        matches++;
    };

    for (int right = 0; right < s2.size(); right++) {
      update(s2[right], +1); // char enters

      if (right >= k)
        update(s2[right - k], -1); // char leaves
      if (matches == 26)
        return true;
    }
    return false;
  }
};

567_solution1_two_maps.go

package main

func checkInclusion(s1 string, s2 string) bool {
    k := len(s1)
    freq, wfreq := map[byte]int{}, map[byte]int{}
    for i := 0; i < k; i++ {
        freq[s1[i]]++
    }

    need := len(freq) // distinct letters in s1, fixed from here on
    matches := 0      // letters of s1 whose window count equals freq

    // change the window count of c by delta, keeping `matches` in sync
    update := func(c byte, delta int) {
        target, ok := freq[c]
        if !ok {
            return // not in s1: irrelevant
        }
        if wfreq[c] == target {
            matches-- // was matching, about to change
        }
        wfreq[c] += delta
        if wfreq[c] == target {
            matches++ // matches now
        }
    }

    for right := 0; right < len(s2); right++ {
        update(s2[right], +1) // char enters
        if right >= k {
            update(s2[right-k], -1) // char leaves
        }
        if matches == need {
            return true
        }
    }
    return false
}

567_solution2_diff_map.go

package main

func checkInclusion(s1 string, s2 string) bool {
    k := len(s1)
    diff := map[byte]int{}
    mismatched := 0

    // shift a letter's diff by delta, keeping `mismatched` in sync
    update := func(c byte, delta int) {
        if diff[c] == 0 {
            mismatched++ // was balanced, about to break
        }
        diff[c] += delta
        if diff[c] == 0 {
            mismatched-- // now balanced again
        }
    }

    for i := 0; i < k; i++ {
        update(s1[i], -1)
    }

    for right := 0; right < len(s2); right++ {
        update(s2[right], +1) // char enters
        if right >= k {
            update(s2[right-k], -1) // char leaves
        }
        if mismatched == 0 {
            return true
        }
    }
    return false
}

567_solution3_two_arrays.go

package main

func checkInclusion(s1 string, s2 string) bool {
    k := len(s1)
    var freq, wfreq [26]int
    for i := 0; i < k; i++ {
        freq[s1[i]-'a']++
    }

    // matches = number of the 26 letters whose window count equals freq
    matches := 0
    for i := 0; i < 26; i++ {
        if freq[i] == wfreq[i] {
            matches++ // empty window: letters absent from s1 already match
        }
    }

    // change the window count of a letter by delta, keeping `matches` in sync
    update := func(ch byte, delta int) {
        c := ch - 'a'
        if wfreq[c] == freq[c] {
            matches-- // was matching, about to change
        }
        wfreq[c] += delta
        if wfreq[c] == freq[c] {
            matches++ // matches now
        }
    }

    for right := 0; right < len(s2); right++ {
        update(s2[right], +1) // char enters
        if right >= k {
            update(s2[right-k], -1) // char leaves
        }
        if matches == 26 {
            return true
        }
    }
    return false
}

567_solution1_two_maps.java

import java.util.HashMap;
import java.util.Map;

class Solution {
    private Map<Character, Integer> freq, wfreq;
    private int matches;

    public boolean checkInclusion(String s1, String s2) {
        int k = s1.length();
        freq = new HashMap<>();
        wfreq = new HashMap<>();
        for (char c : s1.toCharArray())
            freq.merge(c, 1, Integer::sum);

        int need = freq.size(); // distinct letters in s1, fixed from here on
        matches = 0;            // letters of s1 whose window count equals freq

        for (int right = 0; right < s2.length(); right++) {
            update(s2.charAt(right), +1); // char enters
            if (right >= k)
                update(s2.charAt(right - k), -1); // char leaves
            if (matches == need)
                return true;
        }
        return false;
    }

    // change the window count of c by delta, keeping `matches` in sync
    private void update(char c, int delta) {
        Integer target = freq.get(c);
        if (target == null)
            return; // not in s1: irrelevant
        int count = wfreq.getOrDefault(c, 0);
        if (count == target)
            matches--; // was matching, about to change
        wfreq.put(c, count + delta);
        if (count + delta == target)
            matches++; // matches now
    }
}

567_solution2_diff_map.java

import java.util.HashMap;
import java.util.Map;

class Solution {
    private Map<Character, Integer> diff;
    private int mismatched;

    public boolean checkInclusion(String s1, String s2) {
        int k = s1.length();
        diff = new HashMap<>();
        mismatched = 0;

        for (char c : s1.toCharArray())
            update(c, -1);

        for (int right = 0; right < s2.length(); right++) {
            update(s2.charAt(right), +1); // char enters
            if (right >= k)
                update(s2.charAt(right - k), -1); // char leaves
            if (mismatched == 0)
                return true;
        }
        return false;
    }

    // shift a letter's diff by delta, keeping `mismatched` in sync
    private void update(char c, int delta) {
        int d = diff.getOrDefault(c, 0);
        if (d == 0)
            mismatched++; // was balanced, about to break
        diff.put(c, d + delta);
        if (d + delta == 0)
            mismatched--; // now balanced again
    }
}

567_solution3_two_arrays.java

class Solution {
    private int[] freq, wfreq;
    private int matches;

    public boolean checkInclusion(String s1, String s2) {
        int k = s1.length();
        freq = new int[26];
        wfreq = new int[26];
        for (char ch : s1.toCharArray())
            freq[ch - 'a']++;

        // matches = number of the 26 letters whose window count equals freq
        matches = 0;
        for (int i = 0; i < 26; i++)
            if (freq[i] == wfreq[i])
                matches++; // empty window: letters absent from s1 already match

        for (int right = 0; right < s2.length(); right++) {
            update(s2.charAt(right), +1); // char enters
            if (right >= k)
                update(s2.charAt(right - k), -1); // char leaves
            if (matches == 26)
                return true;
        }
        return false;
    }

    // change the window count of a letter by delta, keeping `matches` in sync
    private void update(char ch, int delta) {
        int c = ch - 'a';
        if (wfreq[c] == freq[c])
            matches--; // was matching, about to change
        wfreq[c] += delta;
        if (wfreq[c] == freq[c])
            matches++; // matches now
    }
}

567_solution1_two_maps.js

class Solution {
  checkInclusion(s1, s2) {
    const k = s1.length;
    const freq = new Map();
    const wfreq = new Map();
    for (const c of s1) freq.set(c, (freq.get(c) ?? 0) + 1);

    const need = freq.size; // distinct letters in s1, fixed from here on
    let matches = 0; // letters of s1 whose window count equals freq

    // change the window count of c by delta, keeping `matches` in sync
    const update = (c, delta) => {
      if (!freq.has(c)) return; // not in s1: irrelevant
      const target = freq.get(c);
      const count = wfreq.get(c) ?? 0;
      if (count === target) matches--; // was matching, about to change
      wfreq.set(c, count + delta);
      if (count + delta === target) matches++; // matches now
    };

    for (let right = 0; right < s2.length; right++) {
      update(s2[right], +1); // char enters
      if (right >= k) update(s2[right - k], -1); // char leaves
      if (matches === need) return true;
    }
    return false;
  }
}

567_solution2_diff_map.js

class Solution {
  checkInclusion(s1, s2) {
    const k = s1.length;
    const diff = new Map();
    let mismatched = 0;

    // shift a letter's diff by delta, keeping `mismatched` in sync
    const update = (c, delta) => {
      const d = diff.get(c) ?? 0;
      if (d === 0) mismatched++; // was balanced, about to break
      diff.set(c, d + delta);
      if (d + delta === 0) mismatched--; // now balanced again
    };

    for (const c of s1) update(c, -1);

    for (let right = 0; right < s2.length; right++) {
      update(s2[right], +1); // char enters
      if (right >= k) update(s2[right - k], -1); // char leaves
      if (mismatched === 0) return true;
    }
    return false;
  }
}

567_solution3_two_arrays.js

class Solution {
  checkInclusion(s1, s2) {
    const k = s1.length;
    const freq = new Array(26).fill(0);
    const wfreq = new Array(26).fill(0);
    for (let i = 0; i < k; i++) freq[s1.charCodeAt(i) - 97]++;

    // matches = number of the 26 letters whose window count equals freq
    let matches = 0;
    for (let i = 0; i < 26; i++)
      if (freq[i] === wfreq[i]) matches++; // empty window: letters absent from s1 already match

    // change the window count of s2[i] by delta, keeping `matches` in sync
    const update = (i, delta) => {
      const c = s2.charCodeAt(i) - 97;
      if (wfreq[c] === freq[c]) matches--; // was matching, about to change
      wfreq[c] += delta;
      if (wfreq[c] === freq[c]) matches++; // matches now
    };

    for (let right = 0; right < s2.length; right++) {
      update(right, +1); // char enters
      if (right >= k) update(right - k, -1); // char leaves
      if (matches === 26) return true;
    }
    return false;
  }
}

567_solution1_two_maps.py

from collections import Counter, defaultdict


class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        k = len(s1)
        freq = Counter(s1)
        wfreq = defaultdict(int)

        need = len(freq)  # distinct letters in s1, fixed from here on
        matches = 0  # letters of s1 whose window count equals freq

        # change the window count of c by delta, keeping `matches` in sync
        def update(c, delta):
            nonlocal matches
            if c not in freq:
                return  # not in s1: irrelevant
            if wfreq[c] == freq[c]:
                matches -= 1  # was matching, about to change
            wfreq[c] += delta
            if wfreq[c] == freq[c]:
                matches += 1  # matches now

        for right in range(len(s2)):
            update(s2[right], 1)  # char enters
            if right >= k:
                update(s2[right - k], -1)  # char leaves
            if matches == need:
                return True
        return False

567_solution2_diff_map.py

from collections import defaultdict


class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        k = len(s1)
        diff = defaultdict(int)
        mismatched = 0

        # shift a letter's diff by delta, keeping `mismatched` in sync
        def update(c, delta):
            nonlocal mismatched
            if diff[c] == 0:
                mismatched += 1  # was balanced, about to break
            diff[c] += delta
            if diff[c] == 0:
                mismatched -= 1  # now balanced again

        for c in s1:
            update(c, -1)

        for right in range(len(s2)):
            update(s2[right], 1)  # char enters
            if right >= k:
                update(s2[right - k], -1)  # char leaves
            if mismatched == 0:
                return True
        return False

567_solution3_two_arrays.py

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        k = len(s1)
        freq = [0] * 26
        wfreq = [0] * 26
        for c in s1:
            freq[ord(c) - ord("a")] += 1

        # matches = number of the 26 letters whose window count equals freq
        # empty window: letters absent from s1 already match
        matches = sum(f == 0 for f in freq)

        # change the window count of a letter by delta, keeping `matches` in sync
        def update(ch, delta):
            nonlocal matches
            c = ord(ch) - ord("a")
            if wfreq[c] == freq[c]:
                matches -= 1  # was matching, about to change
            wfreq[c] += delta
            if wfreq[c] == freq[c]:
                matches += 1  # matches now

        for right in range(len(s2)):
            update(s2[right], 1)  # char enters
            if right >= k:
                update(s2[right - k], -1)  # char leaves
            if matches == 26:
                return True
        return False

567_solution1_two_maps.rs

use std::collections::HashMap;

struct Solution;

impl Solution {
    fn check_inclusion(s1: String, s2: String) -> bool {
        let (a, b) = (s1.as_bytes(), s2.as_bytes());
        let k = a.len();
        let mut freq: HashMap<u8, i32> = HashMap::new();
        let mut wfreq: HashMap<u8, i32> = HashMap::new();
        for &c in a {
            *freq.entry(c).or_insert(0) += 1;
        }

        let need = freq.len(); // distinct letters in s1, fixed from here on
        let mut matches = 0; // letters of s1 whose window count equals freq

        // change the window count of c by delta, keeping `matches` in sync
        // (returns the updated count, since the closure holds `matches` mutably)
        let mut update = |c: u8, delta: i32| {
            if let Some(&target) = freq.get(&c) {
                let count = wfreq.entry(c).or_insert(0);
                if *count == target {
                    matches -= 1; // was matching, about to change
                }
                *count += delta;
                if *count == target {
                    matches += 1; // matches now
                }
            } // else: not in s1, irrelevant
            matches
        };

        for right in 0..b.len() {
            let mut m = update(b[right], 1); // char enters
            if right >= k {
                m = update(b[right - k], -1); // char leaves
            }
            if m == need {
                return true;
            }
        }
        false
    }
}

567_solution2_diff_map.rs

use std::collections::HashMap;

struct Solution;

impl Solution {
    fn check_inclusion(s1: String, s2: String) -> bool {
        let (a, b) = (s1.as_bytes(), s2.as_bytes());
        let k = a.len();
        let mut diff: HashMap<u8, i32> = HashMap::new();
        let mut mismatched = 0;

        // shift a letter's diff by delta, keeping `mismatched` in sync
        // (returns the updated count, since the closure holds `mismatched` mutably)
        let mut update = |c: u8, delta: i32| {
            let d = diff.entry(c).or_insert(0);
            if *d == 0 {
                mismatched += 1; // was balanced, about to break
            }
            *d += delta;
            if *d == 0 {
                mismatched -= 1; // now balanced again
            }
            mismatched
        };

        for &c in a {
            update(c, -1);
        }

        for right in 0..b.len() {
            let mut m = update(b[right], 1); // char enters
            if right >= k {
                m = update(b[right - k], -1); // char leaves
            }
            if m == 0 {
                return true;
            }
        }
        false
    }
}

567_solution3_two_arrays.rs

struct Solution;

impl Solution {
    fn check_inclusion(s1: String, s2: String) -> bool {
        let (a, b) = (s1.as_bytes(), s2.as_bytes());
        let k = a.len();
        let mut freq = [0i32; 26];
        let mut wfreq = [0i32; 26];
        for &c in a {
            freq[(c - b'a') as usize] += 1;
        }

        // matches = number of the 26 letters whose window count equals freq
        // empty window: letters absent from s1 already match
        let mut matches = freq.iter().filter(|&&f| f == 0).count();

        // change the window count of a letter by delta, keeping `matches` in sync
        // (returns the updated count, since the closure holds `matches` mutably)
        let mut update = |ch: u8, delta: i32| {
            let c = (ch - b'a') as usize;
            if wfreq[c] == freq[c] {
                matches -= 1; // was matching, about to change
            }
            wfreq[c] += delta;
            if wfreq[c] == freq[c] {
                matches += 1; // matches now
            }
            matches
        };

        for right in 0..b.len() {
            let mut m = update(b[right], 1); // char enters
            if right >= k {
                m = update(b[right - k], -1); // char leaves
            }
            if m == 26 {
                return true;
            }
        }
        false
    }
}