#include <bits/stdc++.h>
#include <gtest/gtest.h>

using namespace std;

/*
 Leet Code 49. Group Anagrams
   Given an array of strings strs, group the anagrams together. You can return the answer in any order.
 Example 1:
    Input: strs = ["eat","tea","tan","ate","nat","bat"]
    Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
 Explanation:
    There is no string in strs that can be rearranged to form "bat".
    The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.
    The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.

 Constraints:
   1 <= strs.length <= 104
   0 <= strs[i].length <= 100
   
   strs[i] consists of lowercase English letters.

 Solution most preferred in 2024–2026 interviews: frequency-count key
 Sorting gives O(k log k) per string.
 Since input contains only lowercase letters (problem constraint), we can use O(k) key  generation:

 When using character frequencies as the key instead of sorting:
   * Sorting costs O(k log k) per string → total O(n k log k)
   * Counting frequencies is pure linear scan: O(k) per string → total O(n k)

 Since the alphabet is fixed (26 lowercase letters), the key is O(1) size, hashing is
 efficient, and we avoid any comparison-based overhead.
*/

void print(const string&, vector<vector<string>>&);
void print(const string&,  vector<string>&);

#define CLASS_NAME(name) #name

struct ArrayHasher {
    std::size_t operator()(const std::array<int,26>& a) const {
        std::size_t h = 0;
        
        for (auto e : a) {
            h ^= std::hash<int>{}(e)  + 0x9e3779b9 + (h << 6) + (h >> 2);
        }
        return h;
    }
};

class SolutionFirstAttempt {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> result;

        if (strs.size() == 0)
            return result;

        // multimap of sorted anagram key to anagram
        multimap<string,string> multimapOfSortedKeyToStr;
        // set of keys for building the output vector of vectors
        set<string> keys; // create unique keys in multimap, build
                          // result vector using equal_range
        
        // for (auto& k: keys)
        // {
        //     vector<string> v;
        //     auto range = xxx.equal_range(k);
        //     for (auto i = range.first; i != range.second; ++i)
        //         v.push_back(i->second);
        //     result.push_back(v);
        // }
        

        // better impl #1
        //
        // unordered_map + vector<string> instead of multimap + set
        unordered_map<string, vector<string>> anagramGroups;
        
        for (auto& str: strs)
        {
            string key = str;
            sort(key.begin(), key.end());
            anagramGroups[key].push_back(str);
        }

        // better impl #2
        //
        // no sorting of key. key is std::array. Need hash func for std::array       
        unordered_map<array<int,26>, vector<string>, ArrayHasher> anagramGroupsWithArrKey;
        
        for (const string& str : strs) {
            array<int,26> cnt;
            for (char c : str)
                cnt[c-'a']++;
            anagramGroupsWithArrKey[cnt].push_back(str);
        }

        for (auto& [key, anagramGroup] : anagramGroups)
        {
            result.push_back(move(anagramGroup));
        }
        
        return result;
    }
};

class SolutionFreqCountKey {
public:
    string getKey(const string& s) {
        int count[26] = {};
        for (char c : s) count[c-'a']++;
        string key;
        for (int i = 0; i < 26; ++i) {
            key += to_string(count[i]) + "#";   // or ','
        }
        return key;
    }

    // bitset doesn't account for duplicate characters in anagram
    bitset<26> getBitsetKey(const string& s)
    {
        bitset<26> bs;
        for (char c: s) bs.set(c - 'a');
        return bs;
    }

    // array does account for dup chars
    array<int,26> getArrayKey(const string& s)
    {
        array<int,26> cnt{};
        for (char c: s) cnt[c - 'a']++;
        return cnt;
    }

    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> result;

        int width = strs[0].size() + 6;
        
        cout << setw(width) << setfill(' ') << " " << "a b c d e f g h i j k l m n o p q r s t u v w x y z" << endl;
        for (auto& str: strs)
        {
            cout << str << " key: " << getKey(str) << endl;
        }
        
        
        unordered_map<array<int,26>, vector<string>, ArrayHasher> anagramGroupsWithArrKey;
        
        // std array
        cout << setw(20) << setfill('-') << '-' << endl;
        cout << setw(width) << setfill(' ') << " " << "abcdefghijklmnopqrstuvwxyz" << endl;
        for (auto& str: strs)
        {
            array<int,26> cnt = getArrayKey(str);
            anagramGroupsWithArrKey[cnt].push_back(str);
            
            cout << str << " key: ";
            for (auto& i: cnt) cout << i;
            cout << endl;
        }
        
        for (auto& [key, anagramGroup] : anagramGroupsWithArrKey)
        {
            result.push_back(move(anagramGroup));
        }
        
        return result;
    }
    string name() { return CLASS_NAME(SolutionFreqCountKey); }
};

struct SolutionMap
{
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> anagramGroups;
        
        for (auto& str: strs)
        {
            string key = str;
            sort(key.begin(), key.end());
            anagramGroups[key].push_back(str);
        }
        
        vector<vector<string>> result;
        for (auto& [k,v]: anagramGroups)
        {
            result.push_back(v);
        }
        return result;
    
    }
    string name() { return CLASS_NAME(SolutionMap); }
};

struct SolutionStdArray
{
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<array<int,26>, vector<string>, ArrayHasher> groupsWithArrKey;
        
        for (const string& str: strs)
        {            
            array<int,26> key{};
            for (char c: str)  key[c - 'a']++;
            groupsWithArrKey[key].push_back(str);
        }
        
        vector<vector<string>> result;
        for (auto& [k,v]: groupsWithArrKey)
        {
            result.push_back(v);
        }
        return result;
    }
    string name() { return CLASS_NAME(SolutionStdArray); }
};

struct SolutionBitSet
{
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<bitset<26>, vector<string>> groups;

        for (const string& s: strs) {
            bitset<26> mask;
            for (char c : s) mask.set(c - 'a');
            groups[mask].push_back(s);
        }
        
        vector<vector<string>> result;
        for (auto& [k,v]: groups)
        {
            result.push_back(v);
        }
        return result;
    }
    string name() { return CLASS_NAME(SolutionBitSet); }    
};

typedef vector<tuple<vector<string>, vector<vector<string>>>> TestCases;

template<typename Solution> struct Runner
{
    void run(TestCases& testCases)
    {
        Solution s;
        cout << "----------------------------------------------------------------\n";
        cout << s.name() << endl;        
        cout << "----------------------------------------------------------------\n";
        for (auto& testCase: testCases)
        {
            vector<string> input = get<0>(testCase);
            print("input", input);
            vector<vector<string>> result = s.groupAnagrams(get<0>(testCase));
            vector<vector<string>> expected = get<1>(testCase);
            print("expected", expected);        
            print("result: ", result);
            EXPECT_EQ(expected, result);
        }
    }
};

int main(void)
{
    vector<tuple<vector<string>, vector<vector<string>>>> testCases {
        // 1
        {{"eat","tea","tan","ate","nat","bat"},
         { {"bat"}, {"tan","nat"},{"eat","tea","ate"} }
        },
        //2
        {{"filler","refill"},
         { {"filler","refill"} }
        },            
        // 3
        {{""},
         { {""} }
        },            
        // 4
        {{"a"},
         { {"a"} }
        },
    };

    { Runner<SolutionFreqCountKey> runner; runner.run(testCases); }
    { Runner<SolutionMap>          runner; runner.run(testCases); }
    { Runner<SolutionBitSet>       runner; runner.run(testCases); }
    { Runner<SolutionStdArray>     runner; runner.run(testCases); }
    
    return 0;
}

void print(const string& label, vector<string>& v)
{
    cout << label << ": [";
    for (auto& a: v)
    {
        cout << a << ",";
    }
    cout << "]" << endl;
}


void print(const string& label, vector<vector<string>>& v)
{
    cout << label << ": [";
    for (auto& a: v)
    {
        cout << "[";
        for (auto& b: a)
            cout << b << ",";
        cout << "]";
    }
    cout << "]" << endl;
}