using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        //string[] A = new string[] {"ababaa","aaabaa"};

        //int expected = 2;

        string[] A = new string[] {"abcd","cdab","cbad","xyzz","zzxy","zzyx"};

        int expected = 3;

        int result = NumSpecialEquivGroups(A);

        Console.WriteLine("expected: {0}", expected);

        Console.WriteLine("result: {0}", result);

    }

    public static int NumSpecialEquivGroupsBetter(string[] A) {

        HashSet<string> s = new HashSet<string>();

        foreach (string str in A)

        {

            List<char> odds = new List<char>();

            List<char> evens = new List<char>();

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

            {

                if (i % 2 == 0)

                    odds.Add(str[i]);

                else

                    evens.Add(str[i]);

            }

            odds.Sort();

            evens.Sort();

            Console.WriteLine(string.Join("", odds) + string.Join("", evens));

            s.Add(string.Join("", odds) + string.Join("", evens));

        }

        return s.Count;

    }

    public static int NumSpecialEquivGroups(string[] A) {

        int groups = 0;

        do

        {

            Dictionary<char,int> odds = new Dictionary<char,int>();

            Dictionary<char,int> evens = new Dictionary<char,int>();

            for (int i = 0; i < A[0].Length; i++)

            {

                if (i % 2 == 0) {

                    if (odds.ContainsKey(A[0][i]))

                        odds[A[0][i]] += 1;

                    else

                        odds.Add(A[0][i], 1);

                }

                else {

                    if (evens.ContainsKey(A[0][i]))

                        evens[A[0][i]] += 1;

                    else

                        evens.Add(A[0][i], 1);

                }

            }

            Console.WriteLine("\nodds:");

            foreach(KeyValuePair<char,int> entry in odds)

                Console.Write(entry.Key + " " + entry.Value + " ");

            Console.WriteLine("\nevens:");

            foreach(KeyValuePair<char,int> entry in evens)

                Console.Write(entry.Key + " " + entry.Value + " ");

            // odds: ['x',1],['z',1]

            // evens: ['y',1],['z',1]

            Stack<string> stack = new Stack<string>();

            for (int i = 1; i < A.Length; i++)

            {

                Dictionary<char,int> currOdds = new Dictionary<char,int>();

                Dictionary<char,int> currEvens = new Dictionary<char,int>();

                for (int j = 0; j < A[i].Length; j++)

                {

                    if (j % 2 == 0) {

                        if (currOdds.ContainsKey(A[i][j]))

                            currOdds[A[i][j]] += 1;

                        else

                            currOdds.Add(A[i][j], 1);

                    }

                    else {

                        if (currEvens.ContainsKey(A[i][j]))

                            currEvens[A[i][j]] += 1;

                        else

                            currEvens.Add(A[i][j], 1);

                    }

                }

                foreach (KeyValuePair<char,int> entry in currOdds) {

                    if (!odds.ContainsKey(entry.Key) || odds[entry.Key] < entry.Value) {

                        stack.Push(A[i]);

                        break;

                    }

                }

                if (stack.Count == 0 || stack.Peek() != A[i]) {

                    foreach (KeyValuePair<char,int> entry in currEvens) {

                        if (!evens.ContainsKey(entry.Key) || evens[entry.Key] < entry.Value) {

                            stack.Push(A[i]);

                            break;

                        }

                    }

                }

            }

            A = new string[stack.Count];

            while (stack.Count > 0) {

                Console.Write(stack.Peek() + " ");

                A[stack.Count - 1] = stack.Pop();

            }

            groups++;

            Console.WriteLine("\ngroups: " + groups);

        } while (A.Length > 1);

        if (A.Length > 0)

            groups++;

        Console.WriteLine("groups: " + groups);

        return groups;

    }

}