I was preparing some problems for a college contest from the past few weeks and came up with this problem idea.
Given N words consisting of either lowercase English letters or a special character '#'.
Find the expected number of nodes in the trie after a trie is constructed replacing all the special character('#') in the words uniformly randomly with any letter between 'a' to 'z'.
I want to know if there exists any polynomial time solution for this problem.
Thanks