Treasure Hunt Trie

#1

what we do is for all nodes of the trie , we calculate number of strings in the substree and then just apply combinatorics such -
NC2(total nodes in the subtree of current nodes)-summation of NC2(children in each nodes)
unable to explain it that clearly
I didn’t understand How above formula is working

#2
  1. Iterate over the array
  2. For every ith string … just traverse it and for every prefix of it . Just search it in the map if it is already present. If not insert it else just increment the value of map[prefix] ++.
  3. If the count of a certain prefix is suppose x then the total combinations would be x*(x+1)/2. simple xC2 combinatorics.
  4. That’s it now just traverse the map and check for every key its length and the value that it holds i.e the x that is explained above.
#3


Help me with this question

#4

You can check this out.

#5

I have done this question.