#1170

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Compare Strings by Frequency of the Smallest Character

Compare Strings by Frequency of the Smallest Character requires counting minimal character frequencies in words and queries efficiently.

array hash table string binary search sorting

Problem Statement

Given two arrays of non-empty lowercase strings, words and queries, define f(s) as the frequency of the lexicographically smallest character in string s. For example, f("dcce") = 2 because 'c' is smallest and appears twice. Your task is to process each query in queries and determine how many words have a strictly higher f value.

Return an integer array answer where answer[i] represents the count of words satisfying f(queries[i]) < f(W) for each W in words. Constraints include up to 2000 queries and words, each string up to length 10, consisting of lowercase letters only.

Examples

Example 1

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

Output: [1]

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

Example 2

Input: queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]

Output: [1,2]

On the first query only f("bbb") f("cc").

Constraints

1 <= queries.length <= 2000
1 <= words.length <= 2000
1 <= queries[i].length, words[i].length <= 10
queries[i][j], words[i][j] consist of lowercase English letters.

Solution Approach

Precompute Word Frequencies

Scan each string in words to compute f(W) and store the results in an integer array. Sorting this array enables faster comparison later, turning multiple string scans into efficient numeric lookups.

Evaluate Queries

For each query string, compute f(query) using the same scanning method. Use the precomputed sorted word frequencies to count how many are strictly larger, either via binary search or a simple iteration, directly leveraging the array scanning plus hash lookup pattern.

Optimize for Multiple Queries

Since words are static, sorting their frequencies once and reusing the array avoids redundant computation. This trade-off balances time and space, ensuring that handling up to 2000 queries remains efficient while maintaining clarity in the scanning and counting logic.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(NlogN + MlogN) where N is the number of words and M is the number of queries, due to sorting word frequencies and querying each. Space complexity is O(N) for storing word frequency counts.

What Interviewers Usually Probe

Do you precompute any values for words to avoid repeated work?
Can you explain how array scanning and frequency counting connect to the hash lookup?
How would you handle very large queries efficiently without scanning words repeatedly?

Common Pitfalls or Variants

Common pitfalls

Forgetting to count only strictly greater frequencies for queries.
Recomputing f(W) for each query instead of precomputing and reusing.
Mishandling edge cases where multiple characters tie as the smallest in a word.

Follow-up variants

Return counts where f(queries[i]) <= f(W) instead of strictly less than.
Find the maximum difference f(W) - f(query) for each query.
Handle uppercase and lowercase letters with same frequency comparison logic.

FAQ

How do I calculate f(s) for a string?

Scan the string to find the lexicographically smallest character and count its occurrences; this gives f(s).

Why precompute word frequencies instead of comparing each query directly?

Precomputing and sorting frequencies allows O(logN) comparisons per query instead of scanning all words repeatedly, improving efficiency.

Can I use a hash map instead of sorting?

Yes, a hash map of frequency counts works, but sorting simplifies counting how many words exceed a given frequency and aligns with the array scanning plus hash lookup pattern.

What if multiple characters are tied for smallest in a string?

Pick the lexicographically smallest character among them and count only its frequency for f(s).

Does this approach handle the LeetCode problem Compare Strings by Frequency of the Smallest Character efficiently?

Yes, by precomputing word frequencies and using binary search or scanning for queries, it ensures fast and correct results across all test cases.

terminal

Solution

Solution 1: Sorting + Binary Search

First, according to the problem description, we implement a function $f(s)$, which returns the frequency of the smallest letter in the string $s$ in lexicographical order.

1

2

3

4

5

6

7

8

9

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]

Continue Practicing

#792 number of matching subsequences #1169 invalid transactions #1202 smallest string with swaps