Count Strings with Given Prefixes

Problem: Given N prefixes and M strings (M > N), for each given prefix count the number of strings that start with that prefix.

Constraints: N prefixes, M strings, all lowercase.

Example: prefixes = ["ab", "c"], strings = ["abc", "abd", "cat", "dog"] -> ab: 2, c: 1.

Approach: Build a Trie from all M strings, marking, at each node, how many strings pass through it (a count incremented during insertion). For each prefix, walk the Trie along its characters and read off the count stored at the final node — O(1) per query after O(total string length) Trie construction.