Last active
December 3, 2024 14:28
-
-
Save aannenko/fce2c617454b2fd3936ec86d4a6c77ca to your computer and use it in GitHub Desktop.
How many permutations of one string are there in the other string (hash and counter comparison)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Given a smaller string "pattern" and a bigger string "text", | |
// design an algorithm to find all permutations of the shorter | |
// string within the longer one. Return the location of each permutation. | |
CountPermutations("cbabadcbbabbcbabaabccbabc", "abbc").Dump(); | |
// Output: [0, 6, 9, 11, 12, 20, 21] | |
CountPermutations("encyclopedia", "dep").Dump(); | |
// Output: [7] | |
static IEnumerable<int> CountPermutations(string text, string pattern) | |
{ | |
if (text.Length < pattern.Length) | |
yield break; | |
long patternHash = 0; | |
var patternCounter = new Dictionary<char, int>(text.Length); | |
long windowHash = 0; | |
var windowCounter = new Dictionary<char, int>(text.Length); | |
for (int i = 0; i < pattern.Length; i++) | |
{ | |
patternHash += pattern[i].GetHashCode(); | |
if (!patternCounter.TryAdd(pattern[i], 1)) | |
patternCounter[pattern[i]]++; | |
windowHash += text[i].GetHashCode(); | |
if (!windowCounter.TryAdd(text[i], 1)) | |
windowCounter[text[i]]++; | |
} | |
if (AreDictionariesEqual(patternCounter, windowCounter)) | |
yield return 0; | |
for (int i = pattern.Length; i < text.Length; i++) | |
{ | |
var charOut = text[i - pattern.Length]; | |
windowHash -= charOut.GetHashCode(); | |
var outCount = --windowCounter[charOut]; | |
if (outCount is 0) | |
windowCounter.Remove(charOut); | |
var charIn = text[i]; | |
windowHash += charIn.GetHashCode(); | |
if (!windowCounter.TryAdd(charIn, 1)) | |
windowCounter[charIn]++; | |
if (patternHash == windowHash && AreDictionariesEqual(patternCounter, windowCounter)) | |
yield return i - pattern.Length + 1; | |
} | |
} | |
static bool AreDictionariesEqual(Dictionary<char, int> first, Dictionary<char, int> second) | |
{ | |
if (first.Count != second.Count) | |
return false; | |
foreach (var (chr, firstCount) in first) | |
if (!second.TryGetValue(chr, out var secondCount) || firstCount != secondCount) | |
return false; | |
return true; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment