USACO Silver 2016 December - Cities & States

Java

C++

As the editorial mentions, we can store the number of times a given four-letter string appears in a map.

Time Complexity: $\mathcal{O}(N\log N)$ with map, $\mathcal{O}(N)$ with unordered_map.

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using db = double; 
using str = string; // yay python!

using pi = pair<int,int>;
using pl = pair<ll,ll>;

A faster solution is to convert each string into an integer in the range $[0,26^4)$ and use an array instead of a map.

Time Complexity: $\mathcal{O}(N)$

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using db = double; 
using str = string; // yay python!

using pi = pair<int,int>;
using pl = pair<ll,ll>;