Skip to content

Instantly share code, notes, and snippets.

@aannenko
Last active December 3, 2024 14:28
Show Gist options
  • Save aannenko/fce2c617454b2fd3936ec86d4a6c77ca to your computer and use it in GitHub Desktop.
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)
// 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