Problem Statement:
Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.
In other words, return true if one of s1‘s permutations is the substring of s2.
Examples:
Example 1:
Input: s1 = “ab”, s2 = “eidbaooo”
Output: true
Explanation: s2 contains one permutation of s1 (“ba”).
Example 2:
Input: s1 = “ab”, s2 = “eidboaoo”
Output: false
Constraints:
1 <= s1.length, s2.length <= 104s1ands2consist of lowercase English letters.
Approach
-
Use two frequency arrays
hashSandhashWof size 26 to count character occurrences (assuming lowercase English letters). - Fill both arrays with frequencies from
s1and the first window ofs2of length equal tos1. - Slide the window across
s2one character at a time:- At each step, compare the two frequency arrays using
isHashSame(). - If they match, it means a permutation of
s1is present ins2, so returntrue. - Otherwise, update the window by removing the leftmost character and adding the next character.
- At each step, compare the two frequency arrays using
- If no match is found till the end, return
false.
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(1)
Dry Run
Input: s1 = "ab", s2 = "abcabcbb"
Initialize: → hashS = Array(26).fill(0) → hashW = Array(26).fill(0) → windowLength = 2 Build hash for s1 and first window of s2: i = 0 → s1[0] = 'a' → hashS[0]++ s2[0] = 'a' → hashW[0]++ → hashS = [1, 0, ..., 0] → hashW = [1, 0, ..., 0] i = 1 → s1[1] = 'b' → hashS[1]++ s2[1] = 'b' → hashW[1]++ → hashS = [1, 1, 0, ..., 0] → hashW = [1, 1, 0, ..., 0] Set pointers: → i = 0, j = 1 Start sliding window: j = 1 (window = s2[0..1] = "ab") → isHashSame(hashS, hashW) = true → Return true
Output: Result: true
Visualisation:
var checkInclusion = function(s1, s2) {
if (s1.length > s2.length) return false;
let hashS = Array(26).fill(0);
let hashW = Array(26).fill(0);
let windowLength = s1.length;
for (let i = 0; i < windowLength; i++) {
hashS[s1.charCodeAt(i) - 97]++;
hashW[s2.charCodeAt(i) - 97]++;
}
let i = 0;
let j = windowLength - 1;
while (j < s2.length) {
if (isHashSame(hashS, hashW)) {
return true;
}
hashW[s2.charCodeAt(i) - 97]--;
i++;
j++;
if (j < s2.length) {
hashW[s2.charCodeAt(j) - 97]++;
}
}
return false;
};
var isHashSame = function(hashS, hashW) {
for (let i = 0; i < 26; i++) {
if (hashS[i] !== hashW[i]) {
return false;
}
}
return true;
};
def is_hash_same(a, b):
return a == b
def checkInclusion(s1, s2):
if len(s1) > len(s2):
return False
hashS = [0] * 26
hashW = [0] * 26
window_length = len(s1)
for i in range(window_length):
hashS[ord(s1[i]) - ord('a')] += 1
hashW[ord(s2[i]) - ord('a')] += 1
i = 0
j = window_length - 1
while j < len(s2):
if is_hash_same(hashS, hashW):
return True
hashW[ord(s2[i]) - ord('a')] -= 1
i += 1
j += 1
if j < len(s2):
hashW[ord(s2[j]) - ord('a')] += 1
return False
public class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) return false;
int[] hashS = new int[26];
int[] hashW = new int[26];
int windowLength = s1.length();
for (int i = 0; i < windowLength; i++) {
hashS[s1.charAt(i) - 'a']++;
hashW[s2.charAt(i) - 'a']++;
}
int i = 0, j = windowLength - 1;
while (j < s2.length()) {
if (isHashSame(hashS, hashW)) return true;
hashW[s2.charAt(i) - 'a']--;
i++;
j++;
if (j < s2.length())
hashW[s2.charAt(j) - 'a']++;
}
return false;
}
private boolean isHashSame(int[] a, int[] b) {
for (int i = 0; i < 26; i++) {
if (a[i] != b[i]) return false;
}
return true;
}
}
#include <iostream>
#include <vector>
#include <string>
using namespace std;
bool isHashSame(vector& a, vector& b) {
for(int i = 0; i < 26; i++) {
if(a[i] != b[i]) return false;
}
return true;
}
bool checkInclusion(string s1, string s2) {
if(s1.length() > s2.length()) return false;
vector hashS(26, 0), hashW(26, 0);
int window_length = s1.length();
for(int i = 0; i < window_length; i++) {
hashS[s1[i] - 'a']++;
hashW[s2[i] - 'a']++;
}
int i = 0, j = window_length - 1;
while(j < s2.length()) {
if(isHashSame(hashS, hashW)) return true;
hashW[s2[i] - 'a']--;
i++;
j++;
if(j < s2.length())
hashW[s2[j] - 'a']++;
}
return false;
}
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool isHashSame(int *a, int *b) {
for(int i = 0; i < 26; i++) {
if(a[i] != b[i]) return false;
}
return true;
}
bool checkInclusion(char *s1, char *s2) {
int len1 = strlen(s1), len2 = strlen(s2);
if(len1 > len2) return false;
int hashS[26] = {0}, hashW[26] = {0};
for(int i = 0; i < len1; i++) {
hashS[s1[i] - 'a']++;
hashW[s2[i] - 'a']++;
}
int i = 0, j = len1 - 1;
while(j < len2) {
if(isHashSame(hashS, hashW)) return true;
hashW[s2[i] - 'a']--;
i++;
j++;
if(j < len2)
hashW[s2[j] - 'a']++;
}
return false;
}
using System;
class Solution {
public bool CheckInclusion(string s1, string s2) {
if (s1.Length > s2.Length) return false;
int[] hashS = new int[26];
int[] hashW = new int[26];
int window_length = s1.Length;
for (int i = 0; i < window_length; i++) {
hashS[s1[i] - 'a']++;
hashW[s2[i] - 'a']++;
}
int i = 0, j = window_length - 1;
while (j < s2.Length) {
if (IsHashSame(hashS, hashW)) return true;
hashW[s2[i] - 'a']--;
i++;
j++;
if (j < s2.Length)
hashW[s2[j] - 'a']++;
}
return false;
}
private bool IsHashSame(int[] a, int[] b) {
for (int i = 0; i < 26; i++) {
if (a[i] != b[i]) return false;
}
return true;
}
}
