[Solution] 2-Letter Strings solution codeforces

2-Letter Strings solution codeforces – Given 𝑛n strings, each of length 22, 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.

[Solution] 2-Letter Strings solution codeforces

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𝑝21≤p≤2) such that 𝑠𝑖𝑝𝑠𝑗𝑝sip≠sjp.

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𝑡1001≤t≤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𝑛1051≤n≤105) — the number of strings.

Then follows 𝑛n lines, the 𝑖i-th of which containing a single string 𝑠𝑖si of length 22, consisting of lowercase Latin letters from ‘a‘ to ‘k.

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 105105.

[Solution] 2-Letter Strings solution codeforces

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𝑝21≤p≤2) such that 𝑠𝑖𝑝𝑠𝑗𝑝sip≠sjp.

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++).

Example
input

Copy
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
output

Copy
5
6
0
6

2-Letter Strings solution codeforces

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.

For Solution

Click here

Leave a Comment