Skip to main content
Talentd

Compare Strings by Frequency of the Smallest Character - Solution & Explanation

MediumArrayHash TableStringBinary Search12 min readAsked at: Google
Practice this problem

Problem Statement

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.

You are given an array of strings words and another array of query strings queries. For each query queries[i], count the number of words in words such that f(queries[i]) < f(W) for each W in words.

Return an integer array answer, where each answer[i] is the answer to the ith query.

 

Example 1:

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").

Example 2:

Input: queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
Output: [1,2]
Explanation: On the first query only f("bbb") < f("aaaa"). On the second query both f("aaa") and f("aaaa") are both > 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.

Approach Overview

Problem Overview: Each string has a value f(s), defined as the frequency of its smallest character. For every query string, count how many words have a strictly larger f(s). The challenge is avoiding repeated comparisons across two lists of strings.

Approach 1: Naive Frequency Comparison (Brute Force) (Time: O(Q * W * L), Space: O(1))

Compute f(s) by scanning the string, finding the smallest character, then counting how many times it appears. For each query, iterate through every word and recompute f(word). If f(word) > f(query), increment the count. This approach uses simple iteration and string processing with no additional data structures. It works for small inputs but becomes slow because every comparison recomputes frequencies and scans the entire words array.

Approach 2: Precompute + Sorting with Binary Search (Time: O((Q + W) * L + W log W + Q log W), Space: O(W))

First compute f(word) for every word and store the values in an array. Sort this array. Now for each query, compute f(query) once and use binary search to find the first index where the stored frequency is greater than the query value. The number of valid words becomes len(wordsFreq) - index. Sorting enables logarithmic lookup instead of scanning the entire list each time. This technique combines preprocessing with efficient lookups using sorting and binary search.

Computing f(s) itself is straightforward: iterate over the string, track the smallest character, then count its occurrences. Since strings contain only lowercase letters, the operation runs in O(L) time where L is the string length. Problems like this often appear in interview sets focused on array processing and string analysis.

Recommended for interviews: The preprocessing + binary search approach. Interviewers expect you to notice repeated work in the brute force method and eliminate it by precomputing word frequencies. Sorting once and answering each query in logarithmic time demonstrates strong algorithmic thinking.

Approach 1: Naive Approach

This approach involves calculating the frequency of the lexicographically smallest character for each query and each word. Then, for each query, we count how many words have a frequency greater than the frequency of the query.

This function computes f(s) for both queries and words, and compares the frequencies. It iterates over each query and calculates how many times the word frequency is greater than the query frequency.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n * m) where n is the length of queries and m is the length of words.
Space Complexity: O(m) for storing words frequencies.

Try this approach in the editor →

Approach 2: Optimized with Binary Search

This approach first computes the frequency for all words and stores them in a list. Then, it sorts this list to enable binary search. For each query, we determine using binary search how many word frequencies are greater than the query frequency.

We compute and sort the frequency list of words and use binary search to find the position where the query's frequency would fit. The difference provides the count of higher frequencies.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(m log m + n log m) where n is the length of queries and m is the length of words.
Space Complexity: O(m) for storing sorted words frequencies.

Try this approach in the editor →

Approach 3: 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.

Next, we calculate f(w) for each string w in words, sort them, and store them in an array nums.

Then, we traverse each string q in queries, and binary search in nums for the first position i that is greater than f(q). Then, the elements at index i and after in nums all satisfy f(q) < f(W), so the answer to the current query is n - i.

The time complexity is O((n + q) times M), and the space complexity is O(n). Here, n and q are the lengths of the arrays words and queries respectively, and M is the maximum length of the strings.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Naive Approach

Time Complexity: O(n * m) where n is the length of queries and m is the length of words.
Space Complexity: O(m) for storing words frequencies.

Optimized with Binary Search

Time Complexity: O(m log m + n log m) where n is the length of queries and m is the length of words.
Space Complexity: O(m) for storing sorted words frequencies.

Sorting + Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive Frequency ComparisonO(Q * W * L)O(1)Small datasets or when optimizing code simplicity over performance
Precompute + Sorting with Binary SearchO((Q + W) * L + W log W + Q log W)O(W)General case with many queries where repeated comparisons must be avoided

Video Solution

1170 Compare Strings by Frequency of the Smallest Character • Kelvin Chandra • 2,688 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Compare Strings by Frequency of the Smallest Character easy or hard?
The problem is rated Medium because the brute force idea is simple but inefficient. The main difficulty is recognizing the repeated work and restructuring the solution with preprocessing, sorting, and binary search to achieve much better performance.
Compare Strings by Frequency of the Smallest Character Python/Java solution
In both Python and Java, compute f(s) by scanning the string and counting the smallest character. Store all word frequencies in a list or array, sort it, then use binary search (bisect in Python or Arrays.binarySearch/custom upper bound in Java) to find how many frequencies exceed the query value.
How to solve Compare Strings by Frequency of the Smallest Character in O(n)?
Pure O(n) comparison per query is possible only if you precompute all word frequencies and store them in a bounded frequency bucket (since the maximum string length is small). Counting frequencies in buckets allows prefix sums to determine how many values are greater than a query frequency. This removes binary search but still requires preprocessing.
What is the best approach for Compare Strings by Frequency of the Smallest Character?
The most efficient approach precomputes the frequency f(s) for every word, stores those values in an array, sorts it, and then answers each query using binary search. For a query frequency f(q), locate the first value greater than it and count the remaining elements. This reduces the query step to O(log W) instead of scanning all words.
Is Compare Strings by Frequency of the Smallest Character asked at Google/Amazon/Meta?
This problem appears frequently in interview preparation sets and has been associated with companies like Google and Amazon in coding practice platforms. It tests string processing, preprocessing strategies, and efficient lookup techniques such as sorting and binary search.
What data structure is used in Compare Strings by Frequency of the Smallest Character?
The optimized approach primarily uses arrays to store frequency values and relies on sorting plus binary search for efficient queries. Some implementations also use counting arrays or prefix sums when exploiting the limited range of possible frequencies.
What is the time complexity of Compare Strings by Frequency of the Smallest Character?
The optimized solution runs in O((Q + W) * L + W log W + Q log W), where Q is the number of queries, W is the number of words, and L is the average string length. Computing the smallest-character frequency takes O(L), sorting takes O(W log W), and each query uses O(log W) binary search.

Ready to solve this problem?

Practice Compare Strings by Frequency of the Smallest Character with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays