You are given three arrays of the same length n:
queries[i]
: a non-empty string representing the text of the i-th query.
timestamps[i]
: an integer representing the time when
queries[i]
was issued.
0 <= i < n
.
You are also given an array prefixes of length m, where each prefixes[j] is a non-empty string.
For each prefix p in prefixes, you must find all distinct query strings that start with p (i.e., query.startsWith(p)), then sort those distinct queries by:
queries
.
q
, look at all indices
k
where
queries[k] == q
and take
min(timestamps[k])
; the query with the smaller earliest timestamp comes first.
Return, for each prefix prefixes[j], the list of matching query strings sorted according to the above rules.
Assume:
1 <= n, m <= 2 * 10^5
(large enough that an (O(nm)) solution will time out).
1 <= len(queries[i]), len(prefixes[j]) <= 50
.
timestamps[i]
fit in a 32-bit signed integer.
You may return the result in any reasonable structure; for example, an array result of length m, where result[j] is a list of strings for prefix prefixes[j].
Example
Input:
queries = ["apple", "app", "banana", "app", "application"]
timestamps = [5, 3, 10, 7, 8]
prefixes = ["ap", "app", "b"]
Processing:
"ap"
:
"apple"
,
"app"
,
"app"
,
"application"
.
"app"
: appears 2 times, earliest timestamp =
min(3, 7) = 3
.
"apple"
: appears 1 time, earliest timestamp =
5
.
"application"
: appears 1 time, earliest timestamp =
8
.
"app"
(freq 2), then
"apple"
(freq 1, time 5), then
"application"
(freq 1, time 8).
"app"
:
"apple"
,
"app"
,
"app"
,
"application"
(same set as above since all start with "app").
"ap"
.
"b"
:
"banana"
only, with frequency 1 and earliest timestamp 10.
Output (conceptually):
"ap"
:
["app", "apple", "application"]
"app"
:
["app", "apple", "application"]
"b"
:
["banana"]