Finding Substring Anagrams

AnagramSingleWord.cs

using System;
using System.Collections.Generic;
using System.Linq;

public static class AnagramInSingleWord
{
    private static void AddToSubstringDictionary(
        string s, Tuple<int, int> startAndLength,
        IDictionary<Tuple<int, int>, string> substrings
    )
    {
        if (startAndLength.Item2 > 0 && substrings.TryGetValue(startAndLength, out string substring) == false)
        {
            substrings.Add(startAndLength, s.Substring(startAndLength.Item1, startAndLength.Item2));
        }
    }

    private static void GenerateSubStrings(
        string s,
        Tuple<int, int> startAndLength,
        IDictionary<Tuple<int, int>, string> substrings
    )
    {
        if (substrings.ContainsKey(startAndLength))
        {
            return;
        }

        if (startAndLength.Item2 == 0)
        {
            return;
        }

        Tuple<int, int> chompLeftCoordinates = Tuple.Create(startAndLength.Item1 + 1, startAndLength.Item2 - 1);
        Tuple<int, int> chompRightCoordinates = Tuple.Create(startAndLength.Item1, startAndLength.Item2 - 1);

        GenerateSubStrings(s, chompLeftCoordinates, substrings);
        GenerateSubStrings(s, chompRightCoordinates, substrings);

        AddToSubstringDictionary(s, chompLeftCoordinates, substrings);
        AddToSubstringDictionary(s, chompRightCoordinates, substrings);
    }

    private static bool IsPairAccountedFor(
        Tuple<int, int> a,
        Tuple<int, int> b,
        HashSet<HashSet<Tuple<int, int>>> pairs
    )
    {
        foreach (HashSet<Tuple<int, int>> pair in pairs)
        {
            if (pair.Contains(a) && pair.Contains(b))
            {
                return true;
            }
        }

        return false;
    }

    private static bool IsAnagram(string a, string b, IDictionary<string, HashSet<string>> anagramBagMap)
    {
        if (a.Length != b.Length)
        {
            return false;
        }

        if (anagramBagMap.TryGetValue(a, out HashSet<string> anagramBag))
        {
            if (anagramBag.Contains(b))
            {
                return true;
            }
        }

        IDictionary<char, int> aCharMap = new Dictionary<char, int>();
        IDictionary<char, int> bCharMap = new Dictionary<char, int>();

        for (int i = 0; i < a.Length; i++)
        {
            if (aCharMap.ContainsKey(a[i]) == false)
            {
                aCharMap.Add(a[i], 0);
            }
            aCharMap[a[i]] += 1;

            if (bCharMap.ContainsKey(b[i]) == false)
            {
                bCharMap.Add(b[i], 0);
            }
            bCharMap[b[i]] += 1;
        }

        foreach (var kvp in aCharMap)
        {
            if (bCharMap.TryGetValue(kvp.Key, out int numCharsInB) == false || kvp.Value != numCharsInB)
            {
                return false;
            }
        }

        if (anagramBagMap.TryGetValue(a, out HashSet<string> aStringAnagramBag) == false)
        {
            aStringAnagramBag = new HashSet<string>();
            anagramBagMap.Add(a, aStringAnagramBag);
        }
        aStringAnagramBag.Add(b);

        if (anagramBagMap.TryGetValue(b, out HashSet<string> bStringAnagramBag) == false)
        {
            bStringAnagramBag = new HashSet<string>();
            anagramBagMap.Add(b, bStringAnagramBag);
        }
        bStringAnagramBag.Add(a);

        return true;
    }

    public static int NumberOfAnagrams(string s)
    {
        IDictionary<Tuple<int, int>, string> substrings = new Dictionary<Tuple<int, int>, string>();
        GenerateSubStrings(s, Tuple.Create(0, s.Length), substrings);

        HashSet<HashSet<Tuple<int, int>>> anagramPairs = new HashSet<HashSet<Tuple<int, int>>>();
        IDictionary<string, HashSet<string>> anagramBag = new Dictionary<string, HashSet<string>>();
        foreach (KeyValuePair<Tuple<int, int>, string> substringTuple in substrings)
        {
            foreach (KeyValuePair<Tuple<int, int>, string> otherSubstringTuple in substrings.Where(t => t.Key.Equals(substringTuple.Key) == false))
            {
                if (IsPairAccountedFor(substringTuple.Key, otherSubstringTuple.Key, anagramPairs) == false &&
                    IsAnagram(substringTuple.Value, otherSubstringTuple.Value, anagramBag))
                {
                    var localPair = new HashSet<Tuple<int, int>>();
                    localPair.Add(substringTuple.Key);
                    localPair.Add(otherSubstringTuple.Key);
                    anagramPairs.Add(localPair);
                }
            }
        }

        return anagramPairs.Count();
    }
}