Anagrams Task

sherlockAndAnagrams.cs

using System.Collections.Generic;
using System.IO;
using System;

class Solution
{

  // Complexity n*n*n*m
	// Complete the sherlockAndAnagrams function below.
	static int sherlockAndAnagrams(string s)
	{
		//Space Complexity can be reduced by maintaining only the last raw
		var cache = new Dictionary<char, int>[s.Length, s.Length];
		int count = 0;
		for (var k = 1; k < s.Length; k++)
		{
			for (var i = 0; i + k - 1 < s.Length; i++)
			{
				cache[i, i + k - 1] = CreateHash(k == 1 ? null : cache[i, i + k - 2], s[i + k - 1]);
			}

			for (var i = 0; i + k - 1 < s.Length; i++)
			{
				for (var j = i + 1; j + k - 1 < s.Length; j++)
				{
					if (IsMatch(cache[i, i + k - 1], cache[j, j + k - 1]))
						count++;
				}
			}
		}

		return count;
	}

	public static bool IsMatch(Dictionary<char, int> d1, Dictionary<char, int> d2)
	{
		if (d1.Count != d2.Count)
			return false;

		foreach (var k in d1.Keys)
		{
			if (!d2.ContainsKey(k) || d1[k] != d2[k])
				return false;
		}

		return true;
	}

	public static Dictionary<char, int> CreateHash(Dictionary<char, int> d1, char c)
	{
		var result = new Dictionary<char, int>();
		if (d1 != null)
		{
			foreach (var k in d1.Keys)
			{
				result[k] = d1[k];
			}
		}

		if (result.ContainsKey(c))
			++result[c];
		else
			result[c] = 1;

		return result;
	}
}