Anagrams

#include <string>
#include <vector>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

typedef std::pair<int, int> pair;

struct pair_hash
{
    template <class T1, class T2>
    std::size_t operator() (const std::pair<T1, T2> &pair) const
    {
        return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
    }
};

template <typename T>
void print_array(std::vector<T> const &v) {
  for (auto x: v) {
    std::cout << x << " ";
  }

  std::cout << std::endl;
}

int main(void) {
  int n;

  std::cin >> n;
  std::vector<std::string> words(n);
  std::vector<std::string> words_sorted(n);
  std::unordered_map<std::string, std::vector<int>> map(n);

  for (int i = 0; i < n; ++i) {
    std::cin >> words[i];
    std::string sorted = words[i];

    std::sort(sorted.begin(), sorted.end());

    map[sorted].push_back(i);
  }

  // Then just print out the words in each set
  // of size > 1
  for (auto it = map.begin(); it != map.end(); ) {
    if (it->second.size() < 2) {
      it = map.erase(it);
    } else{
      ++it;
    }
  }

  std::cout << map.size() << std::endl;

  for (auto it = map.begin(); it != map.end(); ++it) {
    auto s = it->second;
    std::cout << s.size() << std::endl;
    for (auto const &wi: s) {
      std::cout << words[wi] << std::endl;
    }
  }
}

#if 0

int main(void) {
  int n;

  std::cin >> n;
  std::vector<std::string> words(n);

  for (int i = 0; i < n; ++i) {
    std::cin >> words[i];
  }

  // Simpler approach, just maintain sets and iterate through each set
  std::vector<std::vector<char>> sets;
  std::vector<std::vector<int>> set_words;

  for (unsigned int k = 0; k < words.size(); ++k) {
    std::vector<char> key(26);
    bool found = false;
    int checked = 0;
    for (char c: words[k]) {
      key[(int) (c - 'a')] += 1;
      checked |= (1 << (c - 'a'));
    }

    for (unsigned int i = 0; i < sets.size(); ++i) {
      bool eq = true;

      // Go through the key in the order of the letters
      // of the word, you'll very quickly determine if
      // there is a mismatch
      for (char c: words[k]) {
        int j = (int) c - 'a';
        if (sets[i][j] != key[j]) {
          eq = false;
          break;
        }

        checked &= ~((1 << (c - 'a')));

        if (checked == 0) {
          break;
        }
      }

      if (eq) {
        // If we get to here, then the two keys are equal, add this word to the set
        set_words[i].push_back(k);
        found = true;
        break;
      }
    }

    if (!found) {
      auto s = std::vector<int>(1);
      s[0] = k;

      set_words.push_back(s);
      sets.push_back(key);
    }
  }

  // Then just print out the words in each set
  // of size > 1
  int sg1 = 0;
  for (unsigned int i = 0; i < set_words.size(); ++i) {
    if (set_words[i].size() > 1) {
      sg1 += 1;
    }
  }

  std::cout << sg1 << std::endl;

  for (auto const &s: set_words) {
    if (s.size() > 1) {
      std::cout << s.size() << std::endl;
      for (auto const &wi: s) {
        std::cout << words[wi] << std::endl;
      }
    }
  }
}

#endif

#if 0

int main(void) {
  int n;

  std::cin >> n;
  std::vector<std::string> words(n);

  for (int i = 0; i < n; ++i) {
    std::cin >> words[i];
  }
  

  // We can make a hashtable of words, first compute
  // the hash of every word as just the sum of its characters
  // where there is a match between two words we can compare
  // with an is_anagram function or something like that
  std::vector<long> hashes(n);
  std::vector<size_t> lengths(n);
  for (int i = 0; i < n; ++i) {
    auto const &w = words[i];
    for (char c : w) {
      hashes[i] += (int) (c);
    }
    lengths[i] = w.size();
  }

  // Now that we have the hashes, we can put things into groups
  // where their hashes are equal and they are actually anagrams
  // of each other. This only happens if the words are the same size, I think.
  std::unordered_map<pair, std::vector<int>, pair_hash> ht;

  for (int i = 0; i < n; ++i) {
    auto key = pair(hashes[i], lengths[i]);

    ht[key].push_back(i);
  }

  for (auto it = ht.begin(); it != ht.end();) {
    if (it->second.size() < 2) {
      it = ht.erase(it);
    } else {
      ++it;
    }
  }

  std::cout << ht.size() << std::endl;

  for (auto it = ht.begin(); it != ht.end(); ++it) {
    auto const &idxs = it->second;

    std::cout << it->second.size() << std::endl;

    for (auto const &i: idxs) {
      std::cout << words[i] << std::endl;
    }
  }

  return 0;
}
#endif

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED