Comments

For problem D, you can transform the string into a tree, and you can solve it in O(n).