(Analysis by Nick Wu)

In this problem, we have pairs of cities and states. We want to count the number of "special pairs", where the first two letters of the city in one pair is the state in the other pair and the two cities are in different states.

Because there are up to $2 \cdot 10^5$ cities to consider, we cannot iterate over all possible pairings of cities.

Note that we can reduce a given city/state pair into a four letter string, where the first two letters are the first two letters of the city and the last two letters are the state code. If two cities form a special pair, then it must be the case that the first two letters swap with the last two letters. Also, the first two letters and last two letters cannot be identical. We can store the number of times a given four-letter string appears in a map for an $O(N)$ algorithm.

Here is my Java code:

import java.io.*;
import java.util.*;
public class citystate {
public static void main(String[] args) throws IOException {
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("citystate.out")));
Map<String, Long> count = new HashMap<String, Long>();
for(int i = 0; i < n; i++) {
String city = st.nextToken();
String state = st.nextToken();
if(!city.substring(0, 2).equals(state)) {
String key = city.substring(0, 2) + state;
if(!count.containsKey(key)) {
count.put(key, 0L);
}
count.put(key, count.get(key) + 1);
}
}
long ret = 0;
for(String key: count.keySet()) {
String otherKey = key.substring(2) + key.substring(0, 2);
if(count.containsKey(otherKey)) {
ret += count.get(key) * count.get(otherKey);
}
}
// note that we have double-counted each pair
pw.println(ret / 2);
pw.close();
}
}