Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Sherlock and Anagram - C# solution - SortedDictionary, Hashtable, BigInteger
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.IO;
using System.Numerics;
static class Program
{
static void Main(string[] args)
{
int t = Convert.ToInt32(Console.ReadLine());
BigInteger[] results = new BigInteger[t];
for (int i = 0; i < t; i++)
{
results[i] = UnorderedAnagrams(Console.ReadLine().Trim());
}
for (int i = 0; i < t; i++)
{
Console.WriteLine(results[i]);
}
}
static BigInteger UnorderedAnagrams(string str)
{
Hashtable htPairs = new Hashtable();
for (int len = 1; len <= str.Length; len++)
{
for (int i = 0; i + len <= str.Length; i++)
{
SortedDictionary<char, int> anagram = new SortedDictionary<char, int>();
for (int j = i; j < i + len; j++)
{
if (anagram.ContainsKey(str[j]))
{
anagram[str[j]] = (int)anagram[str[j]] + 1;
}
else
{
anagram.Add(str[j], 1);
}
}
string finalKey = "";
foreach (char key in anagram.Keys)
{
finalKey += key.ToString() + ((int)anagram[key]).ToString();
}
if (!htPairs.ContainsKey(finalKey))
{
htPairs.Add(finalKey, 1);
}
else
{
htPairs[finalKey] = (int)htPairs[finalKey] + 1;
}
}
}
BigInteger finalResult = 0;
foreach (string k in htPairs.Keys)
{
finalResult += Combinatorial((int)htPairs[k], 2);
}
return finalResult;
}
public static BigInteger Combinatorial(long n, long r)
{
if (n < 0 || r < 0 || (n - r) < 0)
{
return 0;
}
return Factorial(n) / (Factorial(r) * Factorial(n - r));
}
public static BigInteger Factorial(long n)
{
if (n < 0)
{
return -1;
}
BigInteger result = 1;
for (BigInteger i = 1; i <= n; i++)
{
result *= i;
}
return result;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment