Permutation in String

medium string hash map two pointers sliding window

Problem

Given two strings s1 and s2, return true if s2 contains a permutation of s1 as a substring.

Inputs1 = "ab", s2 = "eidbaooo"

Outputtrue

"ba" is a permutation of "ab" and appears in s2.

def check_inclusion(s1, s2):
    if len(s1) > len(s2):
        return False
    need = [0]*26
    have = [0]*26
    for ch in s1:
        need[ord(ch) - 97] += 1
    for i, ch in enumerate(s2):
        have[ord(ch) - 97] += 1
        if i >= len(s1):
            have[ord(s2[i - len(s1)]) - 97] -= 1
        if need == have:
            return True
    return False

function checkInclusion(s1, s2) {
  if (s1.length > s2.length) return false;
  const need = new Array(26).fill(0);
  const have = new Array(26).fill(0);
  for (const ch of s1) need[ch.charCodeAt(0) - 97]++;
  for (let i = 0; i < s2.length; i++) {
    have[s2.charCodeAt(i) - 97]++;
    if (i >= s1.length) have[s2.charCodeAt(i - s1.length) - 97]--;
    if (need.every((v, j) => v === have[j])) return true;
  }
  return false;
}

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) return false;
        int[] need = new int[26], have = new int[26];
        for (char ch : s1.toCharArray()) need[ch - 'a']++;
        for (int i = 0; i < s2.length(); i++) {
            have[s2.charAt(i) - 'a']++;
            if (i >= s1.length()) have[s2.charAt(i - s1.length()) - 'a']--;
            if (Arrays.equals(need, have)) return true;
        }
        return false;
    }
}

bool checkInclusion(string s1, string s2) {
    if (s1.size() > s2.size()) return false;
    int need[26] = {0}, have[26] = {0};
    for (char ch : s1) need[ch - 'a']++;
    for (int i = 0; i < (int)s2.size(); i++) {
        have[s2[i] - 'a']++;
        if (i >= (int)s1.size()) have[s2[i - s1.size()] - 'a']--;
        if (memcmp(need, have, sizeof need) == 0) return true;
    }
    return false;
}

Explanation

A permutation of s1 is just any rearrangement of its letters, so what we really care about is the letter counts. A window in s2 is a permutation of s1 exactly when it has the same count of every letter.

We build a need array of 26 slots holding how many of each letter s1 has. Then we slide a window of length len(s1) across s2, keeping a matching have array of the letters currently inside the window.

As index i moves right, we add s2[i] to have. Once the window has grown past size len(s1), we also remove the letter that just fell off the left, s2[i - len(s1)]. That keeps the window a fixed width.

After each step, if have equals need, the current window is a permutation of s1 and we return true. If we finish the scan with no match, we return false.

Example: s1 = "ab", s2 = "eidbaooo". When the window reaches "ba", its counts (one a, one b) match need, so the answer is true.

Time: O(n + 26·n) Space: O(1)