<s>[INST] Finding out this combination In how many ways three non-empty strings of length less than or equal to $N$ using $k$ different characters can be selected so that in each case, among the three strings, no string is prefix (not necessarily proper prefix) of one of the other two strings. 
Example:
Let $N=1,k=3$.
Result will be $6$
$$
[a, b, c]\\
[a, c, b]\\
[b, a, c]\\
[b, c, a]\\
[c, a, b]\\
[c, b, a]\\
$$
I am getting stuck for the "prefix" part. Please help. I am looking for a way that is computationally cheap as much as possible as $N$ could be as big as $10^{9}$ ($k$ will be much smaller though - upto two digits) .
EDIT :
$$
1\le N\le 10^9\\
1\le k\le 50\\
$$
More Example : For $N=2,k=2$ answer is $36$
 [/INST] Too long for a comment:
If $N=1$, then your problem has $k(k-1)(k-2)$ solutions.
If $N=2$, then the string lengths are $(1,1,1),(1,1,2),(1,2,2)$ or $(2,2,2)$.  The number of solutions is   $$F(1,1,1)=k(k-1)(k-2)\\F(1,1,2)=k(k-1)(k-2)k\\F(1,2,2)=k(k-1)k[(k-1)k-1]\\F(2,2,2)=k^2(k^2-1)(k^2-2)$$
respectively.  The total is 
$$F(1,1,1)+3F(1,1,2)+3F(1,2,2)+F(2,2,2)\\=k^6+3k^5-6k^4-8k^3+8k^2+2k$$
In general, it is a polynomial in $k$ of degree $3N$.
It might be simpler to do the problem for two strings, which might give you insights for the three-string problem.
(edited to reflect the change in question)
If $a\leq b\leq c$ then $F(a,b,c)=k^a(k^b-k^{b-a})(k^c-k^{c-a}-k^{c-b})\\
=k^{a+b+c}-k^{b+c}-k^{a+c}-k^{b+c}+k^{b+c-a}+k^c$
$$X(k,N)=6\sum_{a<b<c}F(a,b,c)+3\sum_{a<b}(F(a,a,b)+F(a,b,b))+\sum_aF(a,a,a)$$
The sum of $k^{a+b+c}$ over all string-lengths $(1\leq a\leq N,1\leq b\leq N,1\leq c\leq N)$ is $[(k^{N+1}-k)/(k-1)]^3$.  The sum for $a<b$ of $k^{a+c}$ equals the sum for $a<b$ of $k^{c+(b-a)}$.  So
$$X(k,N)=\frac{(k^{N+1}-k)^3}{(k-1)^3}+6\sum_{b<c}(b-1)(-2k^{b+c}+k^c)\\
+3\sum_{a<b}(-3k^{a+b}+2k^b)\\
+3\sum_{a<b}(-k^{a+b}-2k^{2b}+k^{2b-a}+k^b)\\
+\sum_a(-3k^{2a}+2k^a)
$$
Some simplifying, including the sum of $k^{2b-a}$ equals the sum of $k^{a+b}$, gives
$$X(k,N)=\frac{(k^{N+1}-k)^3}{(k-1)^3}\\+\sum_{a<b}(-12a+3)k^{a+b}\\ 
+\sum_a(-6a+3)k^{2a}\\
+\sum_a(3a^2-1)k^a$$
WolframAlpha can handle each piece, (and gives an answer with a dozen or two terms, not $N$ or $N^2$ terms).
I think it comes to this, but I could easily have made an error:
$$\frac{1}{(k-1)^3(k+3)^2}\left[-2k^4-24k^3-6k^2-2k\right.\\
+k^N((3N^2-1)k^5-(6N+6)k^4+(-6N^2+6N-19)k^3+6Nk^2+(-3N^2+6N+2)k)\\
+k^{2N}(-6Nk^5+(-6N+6)k^4+(6N+12)k^3+(6N+6)k^2)\\
\left.+k^{3N}(k+1)^2\right]$$
</s>