Compare Strings by Frequency of the Smallest Character — LeetCode 1170 Python Solution

The problem

Let the function f(s) be the frequency of the lexicographically smallest character in a non-empty string s. For example, if s = "dcce" then f(s) = 2 because the lexicographically smallest character is 'c', which has a frequency of 2.

Example

Input

queries = ["cbd"], words = ["zaaaz"]

Output

[1]

Explanation

On the first query we have f("cbd") = 1, f("zaaaz") = 3 so f("cbd") < f("zaaaz").

Python solution

class Solution:
    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:
        def f(s: str) -> int:
            cnt = Counter(s)
            return next(cnt[c] for c in ascii_lowercase if cnt[c])

        n = len(words)
        nums = sorted(f(w) for w in words)
        return [n - bisect_right(nums, f(q)) for q in queries]

Complexity

Pattern: Binary Search

Halve the search space each step — over an array, or over the answer itself. LeetCode 1170. Compare Strings by Frequency of the Smallest Character is filed here because LeetCode tags it Binary Search, which is the vocabulary this hub collects.

The binary search guide has the Python template for the pattern and the 254 LeetCode problems that use it.

Related problems