Introduction

Recently I gave the ICCP practice contest 1 where I found one interesting problem. The problem is not publicly available so I am attaching the image of the question.

Problem Statement

However I am also attaching the problem link.

Problem Link

Kindly do read the question first.

My Approach

I did not know it was a Trie question as I have not studied it yet. I found it after I looked at others' submission. My first question was how to handle the queries in logarithmic time. As the query was kind of finding the number of possible strings having a common given prefix. Since the mapping in the question was many-one, I first converted all the strings into the corresponding numbers(in string format only). Then I noticed that the order of given strings doesn't matter so I sorted it.

Handling Queries

As I noticed the order didn't matter so I thought if I could somehow do a binary search on it.

Luckily, I found a way.

First perform a binary search on the vector of strings (sorted) and find the lowest index(l) with the common given prefix.

Similarly perform another binary search on the same vector of strings and find the highest index(h) with the common prefix.

So, the answer would be h-l+1.

You can look at my submission for implementation.

Code

I don't know what is the level of the problem as I am not qualified enough. I just thought of sharing my approach as I found it interesting and different from others.

At the end Thanks to KushKushal for this amazing problem.