Writing an anagram efficiently I know this question has been asked before now but in Python. Recently, I set out to write an anagram in C#. For instance, orchestra can be rearranged into carthorse and the anagram should not have more repeated than the original. The function is meant to check if the two words are the same and return true in this case. I started with putting the two words in two separate dictionaries with the letters as a key and the count as value.

The idea is using a dictionary ensures the keys can not be repeated. Then I looped through the second dictionary (secondString) and checked if each letter existed as a key in the first dictionary (firstString). Additionally, if the letter existed, the code checks if they have the same count. The rest of the code is self-explanatory.

using System;
using System.Collections.Generic;

public class AreAnagrams
{
    public static bool AreStringsAnagrams(string a, string b)
    {
        Dictionary&lt;char,int&gt; firstString = new Dictionary&lt;char,int&gt;();
        Dictionary&lt;char,int&gt; secondString = new Dictionary&lt;char,int&gt;();

        foreach(char character in a)
        {
            if(firstString.ContainsKey(character)== true)
            {
                firstString[character]+=1;
            }
            else
                firstString[character]=1;
        }
        foreach(char character2 in b)
        {
            if(secondString.ContainsKey(character2)== true)
            {
                secondString[character2]+=1;
            }
            else
                secondString[character2]=1;
        }

        foreach(KeyValuePair&lt;char,int&gt; letterValue in secondString)
        {
            if(firstString.ContainsKey(letterValue.Key))
            {
                if(firstString[letterValue.Key] != secondString[letterValue.Key]){

                    return false;
                }
            }
            else
            {
                return false;
            }
        }
        //throw new NotImplementedException("Waiting to be implemented.");
        return  true;
    }

    public static void Main(string[] args)
    {
        Console.WriteLine(AreStringsAnagrams("momdad", "dadmom"));
    }
}


But I scored 75% and I feel this can be improved on. Also, is there any easy conversion from string to dictionary?
I took your new code and cleaned it up a bit by


adjusting bracket location
removed unnecessary nesting of if statements
gave some operations some breathing room
fixed some odd indentations


I took your code


using System;
using System.Collections.Generic;

public class AreAnagrams
{
    public static bool AreStringsAnagrams(string a, string b)
    {
      Dictionary&lt;char,int&gt; firstString = new Dictionary&lt;char,int&gt;();
      Dictionary&lt;char,int&gt; secondString = new Dictionary&lt;char,int&gt;();

      foreach(char character in a)
      {
          if(firstString.ContainsKey(character))
          {
              firstString[character]+=1;
          }
          else{
              firstString[character]=1;
              }
      }

      foreach(char character2 in b)
      {
          if(secondString.ContainsKey(character2))
          {
              secondString[character2]+=1;
          }
          else{
              secondString[character2]=1;
              }
      }


      if(firstString.Count !=secondString.Count){
          return false;
      }
      else   {
              foreach(KeyValuePair&lt;char,int&gt; letterValue in secondString)
                  {
                      if(firstString.ContainsKey(letterValue.Key))
                      {
                          if(firstString[letterValue.Key] != secondString[letterValue.Key]){

                              return false;
                              }
                      }
                      else
                      {
                          return false;
                      }
                  }
              }
      return  true;
  }

  public static void Main(string[] args)
  {
      Console.WriteLine(AreStringsAnagrams("momdad", "dadmom"));
  }
}



and refactored it to this (there is an issue with the if then statement inside last for loop, which I address later)

public class AreAnagrams
{
    public static bool AreStringsAnagrams(string a, string b)
    {
        Dictionary&lt;char,int&gt; firstString = new Dictionary&lt;char,int&gt;();
        Dictionary&lt;char,int&gt; secondString = new Dictionary&lt;char,int&gt;();

        foreach(char character in a)
        {
            if(firstString.ContainsKey(character))
            {
                firstString[character] += 1;
            }
            else
            {
                firstString[character] = 1;
            }
        }

        foreach(char character2 in b)
        {
            if(secondString.ContainsKey(character2))
            {
                secondString[character2] += 1;
            }
            else
            {
                secondString[character2] = 1;
            }
        }

        if(firstString.Count != secondString.Count)
        {
            return false;
        }
        else   
        {
            foreach(KeyValuePair&lt;char,int&gt; letterValue in secondString)
            {
                if(firstString.ContainsKey(letterValue.Key) 
                    &amp;&amp; (firstString[letterValue.Key] != secondString[letterValue.Key]))
                {
                    return false;
                }
                else
                {
                    return false;
                }
            }
        }
        return  true;
    }

    public static void Main(string[] args)
    {
        Console.WriteLine(AreStringsAnagrams("momdad", "dadmom"));
    }
}




I also decided to change this so that there are two separate if statements, this will reduce the O(n) in the optimistic case
(Your code cleaned up)


foreach(KeyValuePair&lt;char,int&gt; letterValue in secondString)
{
    if(firstString.ContainsKey(letterValue.Key))
    {
        if(firstString[letterValue.Key] != secondString[letterValue.Key]){
            return false;
        }
    }
    else
    {
        return false;
    }
}



New Code with less complexity

foreach(KeyValuePair&lt;char,int&gt; letterValue in secondString)
{
    if (!firstString.ContainsKey(letterValue.Key))
    {
        return false;
    }
    if (firstString[letterValue.Key] != secondString[letterValue.Key])
    {
        return false;
    }
}


You could merge these into a single if statement, but for the sake of reading I left them separate here.  

If one doesn't contain the key of the other one, you want to return false, no need to check the other condition.



Another overall thing that you could do to reduce the O(n) is to evaluate if the strings are the same length, immediately and return false if they are not, because you already know they cannot be anagrams of each other.

like this 

using System;
using System.Collections.Generic;

public class AreAnagrams
{
    public static bool AreStringsAnagrams(string a, string b)
    {
        if (a.Length != b.Length) {
            return false;
        }

        Dictionary&lt;char,int&gt; firstString = new Dictionary&lt;char,int&gt;();
        Dictionary&lt;char,int&gt; secondString = new Dictionary&lt;char,int&gt;();

       /// ...


then you can remove the check later in the code.

I did that, and also changed += 1 to ++ twice in your code.  I also made it case insensitive, but sentences will not work.

Here is the code that works, I tested with your example and with Joker and JReko

if (a.Length != b.Length)
{
    return false;
}

Dictionary&lt;char, int&gt; firstString = new Dictionary&lt;char, int&gt;();
Dictionary&lt;char, int&gt; secondString = new Dictionary&lt;char, int&gt;();

foreach (char character in a.ToLower())
{
    if (firstString.ContainsKey(character))
    {
        firstString[character]++;
    }
    else
    {
        firstString[character] = 1;
    }
}

foreach (char character2 in b.ToLower())
{
    if (secondString.ContainsKey(character2))
    {
        secondString[character2]++;
    }
    else
    {
        secondString[character2] = 1;
    }
}

foreach (KeyValuePair&lt;char, int&gt; letterValue in secondString)
{
    if (!firstString.ContainsKey(letterValue.Key)
        || (firstString[letterValue.Key] != secondString[letterValue.Key]))
    {
        return false;
    }
}

return true;