2-Letter Strings (Codeforces 1669E)
Tags: Math, strings

Given $$$n$$$ strings, each of length $$$2$$$, consisting of lowercase Latin alphabet letters from 'a' to 'k', output the number of pairs of indices $$$(i, j)$$$ such that $$$i < j$$$ and the $$$i$$$-th string and the $$$j$$$-th string differ in exactly one position.In other words, count the number of pairs $$$(i, j)$$$ ($$$i < j$$$) such that the $$$i$$$-th string and the $$$j$$$-th string have exactly one position $$$p$$$ ($$$1 \leq p \leq 2$$$) such that $$${s_{i}}_{p} \neq {s_{j}}_{p}$$$.The answer may not fit into 32-bit integer type, so you should use 64-bit integers like long long in C++ to avoid integer overflow.

Input: The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of strings.Then follows $$$n$$$ lines, the $$$i$$$-th of which containing a single string $$$s_i$$$ of length $$$2$$$, consisting of lowercase Latin letters from 'a' to 'k'.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case, print a single integer — the number of pairs $$$(i, j)$$$ ($$$i < j$$$) such that the $$$i$$$-th string and the $$$j$$$-th string have exactly one position $$$p$$$ ($$$1 \leq p \leq 2$$$) such that $$${s_{i}}_{p} \neq {s_{j}}_{p}$$$. Please note, that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).

Note: For the first test case the pairs that differ in exactly one position are: ("ab", "cb"), ("ab", "db"), ("ab", "aa"), ("cb", "db") and ("cb", "cc").For the second test case the pairs that differ in exactly one position are: ("aa", "ac"), ("aa", "ca"), ("cc", "ac"), ("cc", "ca"), ("ac", "aa") and ("ca", "aa").For the third test case, the are no pairs satisfying the conditions.

Sample Inputs:
4
6
ab
cb
db
aa
cc
ef
7
aa
bb
cc
ac
ca
bb
aa
4
kk
kk
ab
ab
5
jf
jf
jk
jk
jk

Sample Outputs:
5
6
0
6

Solution (Python):
import sys
import copy
import heapq
import bisect
import functools
from math import *
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import groupby
import itertools
from itertools import accumulate
from decimal import Decimal, ROUND_HALF_UP
readline = lambda : sys.stdin.readline().rstrip()

def solve():
    n = int(readline())
    s = [str(readline()) for _ in range(n)]
    mp = defaultdict(int)
    (l, r) = (defaultdict(int), defaultdict(int))
    for i in range(n):
        mp[s[i]] += 1
        l[s[i][0]] += 1
        r[s[i][1]] += 1
    ans = 0
    for (i, (k, v)) in enumerate(l.items()):
        ans += v * (v - 1) // 2
    for (i, (k, v)) in enumerate(r.items()):
        ans += v * (v - 1) // 2
    for (i, (k, v)) in enumerate(mp.items()):
        ans -= v * (v - 1)
    print(ans)

def main():
    t = 1
    t = int(readline())
    for i in range(t):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
    n = int(input())
    prefix = defaultdict(int)
    suffix = defaultdict(int)
    entire = defaultdict(int)
    answer = 0
    for __ in range(n):
        temp = input().strip()
        a = temp[0]
        b = temp[1]
        prefix[a] += 1
        suffix[b] += 1
        entire[temp] += 1
    for (k, v) in prefix.items():
        answer += v * (v - 1) // 2
    for (k, v) in suffix.items():
        answer += v * (v - 1) // 2
    for (k, v) in entire.items():
        answer -= v * (v - 1)
    print(answer)

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
from collections import Counter, defaultdict
from sys import stdin, stdout
import io
import math
import heapq
import bisect
import collections

def ceil(a, b):
    return (a + b - 1) // b
inf = float('inf')

def get():
    return stdin.readline().rstrip()
mod = 10 ** 5 + 7
for _ in range(int(get())):
    n = int(get())
    d1 = defaultdict(int)
    d2 = defaultdict(int)
    ans = 0
    l = []
    for i in range(n):
        s = get()
        d1[s[0]] += 1
        d2[s[1]] += 1
        l.append(s)
    c = Counter(l)
    for i in c:
        ans += (d1[i[0]] - c[i]) * c[i]
        ans += (d2[i[1]] - c[i]) * c[i]
    print(ans // 2)