Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.