using System;

using System.Diagnostics;

using System.Collections.Generic;

using System.Linq;

public class Program

{

    public static void Main()

    {

        var str1 = "abcdef";//gabcdefgabcdefgzxcvb";

        var str2 = "abgfed";//cabgfedcabgfedcbvzcx";

        var sw = new Stopwatch();

​

​

        sw.Start();

        for(int i = 0; i < 1000000; i++)

            NazaRN(str1, str2);                    //linq sequence equal

        sw.Stop();

        Console.WriteLine(sw.ElapsedMilliseconds);

        sw.Reset();

​

        sw.Start();

        for(int i = 0; i < 1000000; i++)

            IdleMind(str1, str2);                  //List<T> removeat

        sw.Stop();

        Console.WriteLine(sw.ElapsedMilliseconds);

        sw.Reset();

​

​

        sw.Start();

        for(int i = 0; i < 1000000; i++)

            CaiusJard1(str1, str2);                //array.sort

        sw.Stop();

        Console.WriteLine(sw.ElapsedMilliseconds);

        sw.Reset(); 

        sw.Start();

        for(int i = 0; i < 1000000; i++)

            CaiusJard1a(str1, str2);               //for loop instead of foreach

        sw.Stop();

        Console.WriteLine(sw.ElapsedMilliseconds);

        sw.Reset(); 

    /*  

        sw.Start();

        for(int i = 0; i < 1000000; i++)

            CaiusJard2(str1, str2);               //preloaded dictionary

        sw.Stop();

        Console.WriteLine(sw.ElapsedMilliseconds);

        sw.Reset();     

        sw.Start();

        for(int i = 0; i < 1000000; i++)

            CaiusJard3(str1, str2);               //containskey dictionary

        sw.Stop();

        Console.WriteLine(sw.ElapsedMilliseconds);

        sw.Reset();

​

        sw.Start();

        for(int i = 0; i < 1000000; i++)

            MattWatson(str1, str2);              //lookup

        sw.Stop();

        Console.WriteLine("MattWatson:" + sw.ElapsedMilliseconds);

        sw.Reset();

*/

​

    }

    static bool NazaRN(string str1, string str2){

        var areEqual = Enumerable.SequenceEqual(str1.OrderBy(c => c), str2.OrderBy(c => c));

        return areEqual;

    }

    static bool CaiusJard1(string str1, string str2){

        if(str1.Length != str2.Length) return false;

​

        var c1 = str1.ToCharArray();

        var c2 = str2.ToCharArray();

        Array.Sort(c1);

        Array.Sort(c2);

​

        for(int i = c1.Length - 1; i >= 0; i--)

          if(c1[i] != c2[i]) return false;

        return true;

    }

    static bool CaiusJard1a(string str1, string str2){

        if(str1.Length != str2.Length) return false;

​

        var counts = new int[26];

        var numPositive = 0;

​

        for(int i = 0; i < str1.Length; i++){

          var r = ++counts[str1[i] - 'a'];

          if(r == 1) numPositive++;

        }

​

        for(int i = 0; i < str2.Length; i++){

          var r = --counts[str1[i] - 'a'];

          if(r < 0) return false;

          if(r == 0) numPositive--;

        }

​

        return numPositive == 0;

    }

    static bool CaiusJard2(string str1, string str2){

        if(str1.Length != str2.Length) return false;

​

        var d = new Dictionary<char, int>();

        var numPositive = 0;

        foreach(var c in str1)

          d[c] = 0;

        foreach(var c in str2)

          d[c] = 0;

        foreach(var c in str1){

          var r = ++d[c];

          if(r == 1) numPositive++;

        }

        foreach(var c in str2){

          var r = --d[c];

          if(r < 0) return false;

          if(r == 0) numPositive--;

        }

​

        return numPositive == 0;

    }

    static bool CaiusJard3(string str1, string str2){

        if(str1.Length != str2.Length) return false;

​

        var d = new Dictionary<char, int>();

        var numPositive = 0;

        foreach(var c in str1){

            if(!d.ContainsKey(c))

                d[c]=0;

            var r = ++d[c];

            if(r == 1) numPositive++;

        }

        foreach(var c in str2){

            if(!d.ContainsKey(c))

                d[c]=0;

            var r = --d[c];

            if(r < 0) return false;

            if(r == 0) numPositive--;

        }

​

        return numPositive == 0;

    }

    static bool IdleMind(string str1, string str2){

        bool stringsAreEqual = (str1.Length == str2.Length);

        if (stringsAreEqual) {

            // see if each char from str1 is in str2, removing from str2 as we go

            List<char> str2chars = new List<char>(str2.ToCharArray());

            foreach (char c in str1.ToCharArray()) {

                int index = str2chars.IndexOf(c);

                if (index != -1) {

                    str2chars.RemoveAt(index);

                }

                else {

                    stringsAreEqual = false;

                    break;

                }

            }

            // any chars left over in str2?

            stringsAreEqual = stringsAreEqual && (str2chars.Count == 0);

        }

        return stringsAreEqual;

    }

    static bool MattWatson(string s1, string s2)

    {

        var lookup1 = s1.ToLookup(ch => ch); // O(N)

        var lookup2 = s2.ToLookup(ch => ch); // O(N)

​

        return lookup1.All(keyValue => // O(N)

            lookup2.Contains(keyValue.Key) && keyValue.Count() == lookup2[keyValue.Key].Count());

    }

}