# Short Permutation in a Long String

• i impove the 4th solution

``````    public class Solution {
public boolean checkInclusion(String s1, String s2) {
int n = s1.length(), m = s2.length();
int[] f = new int[26];
for(int i = 0;i < n;i++){
f[s1.charAt(i)-'a']++;
}
int[] g = new int[26];
for(int i = 0;i < m;i++){
g[s2.charAt(i)-'a']++;
if(i >= n){
g[s2.charAt(i-n)-'a']--;
}
if(Arrays.equals(f, g))return true;
}
return false;
}
}
``````

• Accepted Solution, different logic, no need to compare arrays or maps, just keeping track of length and move window to next possible character for substring, when new character is scanned

public class Solution {
public boolean checkInclusion(String s1, String s2) {
int[] needToFind = new int[256];
int[] hasFound = new int[256];

``````    int s1Len = s1.length();
for (int i = 0; i < s1Len; i++) needToFind[s1.charAt(i)]++;

for (int start=0,end = 0,len=0; start<s2.length() && end < s2.length(); end++) {
char c = s2.charAt(end);
if(needToFind[c]==0) //this character does not exist in original string, so we can scan from next character only and start will be next of this character
{
while(start<end) hasFound[s2.charAt(start++)]--;
start = end+1;
len=0;
}
else{
while (hasFound[c]==needToFind[c]){ //if increased frequency of character is encountered again we need to move window till that character is removed
hasFound[s2.charAt(start++)]--;
len--;
}
hasFound[c]++;
len++;
if(len == s1Len) return true; //if length becomes same to s1 then s2 contains permutation of s1
}
}
return false;
}
``````

}

• More simple Solution:

public boolean checkInclusion(String s1, String s2) {
int [] map = new int [256];
for (char ch : s1.toCharArray()) map [ch] ++;
for (int idx = 0, start = 0; idx < s2.length(); idx ++) {
char ch = s2.charAt (idx);
if (-- map [ch] < 0) while (map [ch] != 0) map [s2.charAt (start ++)] ++;
else if (idx - start + 1 == s1.length()) return true;
}
return false;
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.