gistfile1.txt

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.
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


Note:
The input strings only contain lower case letters.
The length of both given strings is in range [1, 10,000].
Keywords:
Two string s1 s2, 
Ask: return true if s2 contains the permutation of s1, 
requirement: contain a substring 
Variation s1.Length! 
Example: 
String 1: had duplicate char -> 26, counting sort a :1, b: 1
Slide window minimum -> eidboaoo
                                          | -> left, right, index = 0, e not in keys{a,b}
                                           | | | | |
Public 

https://codeshare.io/5PAZnP

Public static bool FindSubstringContainS1Permutation(string search, string keys) 
{
   if(search == null || keys == null)
    return false;
    
   var keysCount = new int[26]; 
      keysCount = addToKeysCount(keys); // keysCount[0] = 1, keywsCount[1] = 1
   Var totalKeysNeed = getTotalKeysNeed(keysCount);
    Var foundCount = new int[26]; 
   Var hashset = new HashSet<int>(keysCount);
   Var left = 0; 
   Var searchLength = search.Length;
  // “aaab”    “aaaab” 
 // keyCount: a -> 3 b->1 
// left -> i: foundCount -> 
// left = 0, i = 0, a->1
// left = 0, i = 1, a->2
// i = 2, a ->3
// i = 3, a->4
   leftChar = ‘a’ <- 
  baaaa
  ||
   foundCount[
   left++         
   Var foundKeyCount = 0;      |
   for(int index = 0; index < searchLength; index++)
{
    Var visit = search[index];
     Var lookupIndex = visit - ‘a’;
    if (!hashSet.Contains(lookIndex))  // C - “ab”
{      left++;
     foundKeyCount  = 0;
       Array.Clear(foundCount); 
        continue;
}
   if(foundCount[lookupIndex ] < keysCount [lookupIndex ])
{ foundKeyCount ++;
foundCount[lookupIndex ]++;
}

// a a a
// a a a a 
// left = 0, i = 3
// left++;
26* n

while(foundCount[lookupIndex ] == keysCount [lookupIndex ])  // slide left pointer if need
{
   Var leftChar = search[left]; 
   Var leftCharIndex = leftChar - ‘a’;
   if(leftCharIndex == lookupIndex)
   {          left++;  //  find ‘a’ from left pointer forward, skip ‘a’. 
             break;   
   }
  Else{
      foundCount[leftCharIndex]--;
       left++;
  }
}
if(foundKeyCount == totalKeysNeed )
  Return true;         
}


bool checkInclusion(string s1, string s2) {
        int hash[26] = {0}, current[26] = {0};
        for (char ch : s1)
            hash[ch-'a']++;
        
        int l = 0, r = -1;
        while (r < (int)s2.length()) {
            if (contain(hash, current)) {
                if (r-l+1 == s1.length()) return true;
                current[s2[l++]-'a']--;
            } else {
                r++;
                if (r < s2.length())
                    current[s2[r]-'a']++;
            }
        }
        return false;
    }
    
    bool contain(int hash[26], int current[26]) {
        for (int i = 0; i < 26; i++) 
            if (current[i] < hash[i])
                return false;
        return true;
    }