# C# primes based O(n) solution

• We will have to use the BigInteger class for this, but no issues it's supported in .NetCore 1.1
Basically, hash strings in prime factorization format .. and divide by s[i] then multiply by s[i+p] to update the new hash .. whenever the hash of s[i..i+p] == hash of p .. then we got a match .. add it ..

``````public class Solution {
private int[] primes = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101 };

public IList<int> FindAnagrams(string s, string p)
{
IList<int> ret = new List<int>();
if (s.Length < p.Length) return ret;

BigInteger h = hash(s.Substring(0, p.Length));
BigInteger hp = hash(p);
for (int i = 0; i <= (s.Length - p.Length); i++)
{
if (h == hp)
{
}

h /= (UInt64)primes[s[i] - 'a'];
h *= ((i + p.Length) < s.Length) ? (UInt64)primes[s[i + p.Length] - 'a'] : 1;
}

return ret;
}

private BigInteger hash(string str)
{
BigInteger h = 1;
foreach (char c in str)
{
h *= (UInt64)primes[c - 'a'];
}

return h;
}
}
``````

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