Compare Strings by Frequency of the Smallest Character

Quick Links

Problem Description

Ah, the age-old question: how many strings are smaller than others based on the frequency of their smallest character? It’s like asking how many people in a room are shorter than the guy who just walked in wearing platform shoes. In this delightful LeetCode problem, you’re tasked with comparing a list of queries against a list of words, all while keeping track of the frequency of the smallest character in each string.

Imagine you’re at a party, and you want to know how many guests are less popular than the one who just got a compliment for their snazzy shoes. You’ll need to count how many people have a smaller number of compliments (or in our case, the frequency of the smallest character).

Code Solution


class Solution:
    def numSmallerByFrequency(
        self,
        queries: list[str],
        words: list[str],
    ) -> list[int]:
        ans = []
        wordsFreq = sorted([word.count(min(word)) for word in words])

        for q in queries:
            count = q.count(min(q))
            index = bisect.bisect(wordsFreq, count)
            ans.append(len(words) - index)

        return ans

Approach Explanation

The code works by first calculating the frequency of the smallest character in each word from the words list and storing these frequencies in a sorted list. For each query, it calculates the frequency of the smallest character and uses binary search to find how many words have a higher frequency. The result is then appended to the answer list.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N log N + M log M), where N is the number of words and M is the number of queries.
Space Complexity	O(N) for storing the frequencies of the words.

Real-World Example

Let’s say you’re at a talent show where contestants are judged based on how many times they can make the audience laugh. The smallest number of laughs (the smallest character frequency) is what you’re interested in. You want to know how many contestants made fewer laughs than the one who just got a standing ovation. This problem is essentially about comparing those laugh counts!