The easy version and the hard version are different problems. However, it is advisable to get the easy version accepted first.

Many place names bear similarities. Take, for instance, $$$\texttt{Suzhou}$$$ and $$$\texttt{Quzhou}$$$. They are considered similar because they share a common substring $$$\texttt{uzhou}$$$. A substring is a contiguous sequence of characters within a string. For example, in the string $$$\texttt{abcd}$$$, $$$\texttt{bc}$$$ is a substring of it, but $$$\texttt{ac}$$$ is not.

We define the similarity between two strings as the length of their longest common substring. Thus, the similarity between $$$\texttt{Suzhou}$$$ and $$$\texttt{Quzhou}$$$ is $$$5$$$, and between $$$\texttt{Hangzhou}$$$ and $$$\texttt{Chengdu}$$$ it is $$$2$$$.

Your task is to construct $$$n$$$ distinct strings of the same length $$$k$$$, composed solely of lowercase English letters. Out of the $$$\frac{n(n-1)}{2}$$$ total pairings between these strings, the maximum similarity should be exactly $$$m$$$.