Sherlock and Anagrams

  • + 0 comments
    public static int sherlockAndAnagrams(string s)
    {
        var allAnagrammaticPairs = 0;
        for(var l = 1; l < s.Length; l++){
            var d = new Dictionary<string, int>();
            for(var i=0; i<s.Length-l+1; i++){
                var ss = new string(s.Substring(i, l).ToCharArray().Order().ToArray());
                if(! d.ContainsKey(ss)) d[ss] = 0;
                d[ss]++;
            }
            var v = d.Values.Where(x => x > 1);
            var combinations = v.Select(x => (x-1)*x/2);
            allAnagrammaticPairs += combinations.Sum();
        }
        return allAnagrammaticPairs;
    }