Lets say I have $2$ strings each having $4$ characters.
$k$ is a number $\le 4$.
If, $2$ strings have exactly $k$ common characters lets say they are a "happy pair" with $k$ points.
If I have $n$ strings how can I find how many happy pairs with point $p$ there are in $O(n)$ ?
General form :
There are $n$ objects. They have some properties $p_1, p_2, p_3,...p_n$.
There are some conditions $c_1, c_2, c_3,....c_k$ for which $p_i = p_j$ ($i$ and $j$ have the same property) where $i \neq j$ and $i,j\le n$
Create a bucket list containing same property holders.
So, if $n = 8$ and $p_3 = p_4 = p_8$ and $p_5 = p_7$ and $p_1 = p_6$
In bucket $1$ I have object $3, 4, 8$.
In bucket $2$ I have object $5, 7$.
In bucket $3$ I have object $1, 6$.
In bucket $4$ I have object $2$.
Now, If I can construct this list in $O(n)$ I can tell how many pairs with property $k$ are there in $O(n)$.
I see the problems of this kind often in programming contests but I don't know how to solve them? If I want to compare two objects I have to check all possible pairs which is $O(n^2)$. So, how to solve these kind of problems in linear time?
What's the strategy to enlist them according to those properties without actually comparing all possible pairs?
For example the string problem,
abcd
ebmd
alcj
if $k = 2$ then $2$ pairs are there.
1) abcd and ebmd (b, d common characters)
2) abcd and alcj (a, c common characters)