Given a list of unique strings, how can I find sum of squares of longest common prefixes length for all pairs.
I think a trie will be useful but I’m not sure how to calculate the final result.
For example, if given strings are and, anacron, anagram, build and buffer
Then possible pairs are (and,anagram) which will give 2 as length of common prefix and squaring it we will get 4
similarly for (anagram,anacron) we will get 3 common prefix and we will add 9 and (and,anacron) will give 4, (build,buffer) will give 2
Other possible pairs will have 0 common prefixes hence they do not contribute.
So final answer will be 4+9+4+4 = 21.
I assume adding length of squares and not the original length is a key to calculate the result.