using System.Collections.Generic;
public static void Main()
string[] A = new string[] {"abcd","cdab","cbad","xyzz","zzxy","zzyx"};
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++)
Console.WriteLine(string.Join("", odds) + string.Join("", evens));
s.Add(string.Join("", odds) + string.Join("", evens));
public static int NumSpecialEquivGroups(string[] A) {
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 (odds.ContainsKey(A[0][i]))
if (evens.ContainsKey(A[0][i]))
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 + " ");
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 (currOdds.ContainsKey(A[i][j]))
currOdds.Add(A[i][j], 1);
if (currEvens.ContainsKey(A[i][j]))
currEvens.Add(A[i][j], 1);
foreach (KeyValuePair<char,int> entry in currOdds) {
if (!odds.ContainsKey(entry.Key) || odds[entry.Key] < entry.Value) {
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) {
A = new string[stack.Count];
while (stack.Count > 0) {
Console.Write(stack.Peek() + " ");
A[stack.Count - 1] = stack.Pop();
Console.WriteLine("\ngroups: " + groups);
Console.WriteLine("groups: " + groups);