Weight by the Earliest Letter

Medium

Define the **weight** of a non-empty string as the number of times its alphabetically earliest letter occurs in it. For example, in "pqqp" the earliest letter is p, so the weight is 2; in "zebra" it is a, so the weight is 1. You get two lists of strings, probes and pool. For each string in probes, count how many strings in pool have a **strictly greater** weight. Return the counts in the same order as probes.

Example 1

probes=["cab", "bbbz"], pool=["xaax", "q", "aaab", "ddd"] → [3, 0]

Weights in pool: in xaax the smallest letter a occurs 2 times, q has 1, aaab has 3, ddd has 3. The weight of cab is 1, so three words are heavier. The weight of bbbz is 3, and no word is heavier.

Example 2

probes=["m"], pool=["zz", "yxy"] → [1]

The weight of m is 1. zz weighs 2, while in yxy the smallest letter x occurs once, so it weighs 1. Only zz is strictly heavier.

Constraints

1 ≤ length of probes ≤ 10⁴
1 ≤ length of pool ≤ 10⁴
1 ≤ length of every string ≤ 10
Strings consist of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table String Binary Search Sorting

Similar problems

Words Hidden in a Text Medium A Square of Unique Labels Medium Anagram Buckets Medium A Subsequence of One Word Only Medium Pairs With a Fixed Gap Medium

Input

probes=["cab", "bbbz"], pool=["xaax", "q", "aaab", "ddd"]

Expected

[3, 0]

Run checks the first 3 tests in your browser. Submit checks all 94 tests on the server, hidden ones included.