Prefix with key greater than X

Problem Description

Design a data structure to efficiently handle Q queries.

1 S K: Insert a string S with key K.

2 S K: find the count of strings having S as prefix and key greater than or equal to K.

Problem Constraints

1 <= Q <= 5e4
1 <= K <= 1e9
sum of S over all query <= 2e5
S consists of lower case english alphabets only

Input Format

First argument is an integer array A of size Q denoting type of query.
Second argument is a string array B of size Q denoting string S for each query.
Third argument is an integer array C of size Q denoting key K for each query.

Output Format

Return an integer array containing all the answer to query 2 in the same order they were asked.

Example Input

Input 1:

    A = [1, 1, 2, 1, 2]
    B = ["abc", "bac", "ab", "abc", "ab"]
    C = [5, 1, 4, 4, 4]

Input 2:

    A = [2]
    B = [a]
    C = [6]

Example Output

Output 1:

    [1, 2]

Output 2:

[0]

Example Explanation

Explanation 1:

    - Insert ["abc", 5]
    - Insert ["bac", 1]
    - string with Key greater than equal 4 having "ab" as prefix is ["abc", 5]; hence answer is 1.
    - Insert ["abc", 4]
    - string with Key greater than equal 4 having "ab" as prefix are ["abc", 5], ["abc", 4]; hence answer is 2

Explanation 2:

    There is no string in data structure so answer is 0.

NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a question? Checkout Sample Codes for more details.

Start solving Prefix with key greater than X on Interview Code Editor

Hints

Hint 1
Solution Approach
Complete Solution

Prefix with key greater than X

Discussion