Compare Strings by Frequency of the Smallest Character Solution
Compare Strings by Frequency of the Smallest Character solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Compare Strings by Frequency of the Smallest Character is a medium coding problem on arrays, strings and hash table, asked in Google and Oracle interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Hash Table, Binary Search
- Asked at: Google, Oracle
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
For a non-empty string w, let f(w) be the number of times its lexicographically smallest letter occurs in it. For example f("kairo") = 1 (one a) and f("dcce") = 2 (two cs).
You are given two string arrays queries and words. For each queries[i], count the words W in words with f(queries[i]) < f(W).
Return an integer array whose i-th element is that count for queries[i].
Example 1
Input: queries = ["kairo","bb"], words = ["a","aa","aaa","aaaa"]
Output: [3,2]
Explanation: f("kairo") = 1, beaten by f = 2, 3 and 4; f("bb") = 2, beaten by f = 3 and 4.
Example 2
Input: queries = ["zz"], words = ["yy","x"]
Output: [0]
Explanation: f("zz") = 2, f("yy") = 2 and f("x") = 1 — neither is larger.
Constraints
1 <= queries.length <= 20001 <= words.length <= 20001 <= queries[i].length, words[i].length <= 10queries[i] and words[i] consist of lowercase English letters
Hints for Compare Strings by Frequency of the Smallest Character
Hint 1
Computing
ftakes one pass: track the smallest letter so far and how often it has appeared.Hint 2
Since every word has length at most 10,
fis between 1 and 10 — bucket the words by theirfvalue.Hint 3
A suffix sum over the buckets answers "how many words have
fgreater than x" in O(1).
How to solve Compare Strings by Frequency of the Smallest Character
f only takes values 1 to 10, so counting words per value and taking suffix sums turns every query into an array lookup.
Approach
- Compute
f(w)for each word in one pass per word and incrementbucket[f(w)]. - Turn the buckets into suffix sums:
atLeast[v] = Σ_{u ≥ v} bucket[u]forvfrom 10 down to 1 (withatLeast[11] = 0). - For each query
q, the answer isatLeast[f(q) + 1].
Why it works
A word is counted for query q exactly when its f value exceeds f(q), i.e. lies in f(q) + 1 … 10; the suffix sum adds precisely those buckets. Sorting the f values and binary searching works equally well when the range is not small.
Complexity
- Time —
O((Q + W) · L) where L ≤ 10 is the string length - Space —
O(1) besides the output
Pitfalls
fcounts the smallest letter, not the most frequent one.- The comparison is strict: words with equal
fare not counted. - Recomputing
ffor every (query, word) pair is O(Q·W·L) — fine for small inputs, slow at 2000 × 2000.
Reference solution
Python
from typing import List
def numSmallerByFrequency(queries: List[str], words: List[str]) -> List[int]:
def f(w):
return w.count(min(w))
at_least = [0] * 12
for w in words:
at_least[f(w)] += 1
for v in range(10, -1, -1):
at_least[v] += at_least[v + 1]
return [at_least[f(q) + 1] for q in queries]Java
public static int[] numSmallerByFrequency(String[] queries, String[] words) {
int[] atLeast = new int[12];
for (String w : words) atLeast[smallestFreq(w)]++;
for (int v = 10; v >= 0; v--) atLeast[v] += atLeast[v + 1];
int[] res = new int[queries.length];
for (int i = 0; i < queries.length; i++) res[i] = atLeast[smallestFreq(queries[i]) + 1];
return res;
}
static int smallestFreq(String w) {
char m = '{';
int c = 0;
for (char x : w.toCharArray()) {
if (x < m) { m = x; c = 1; } else if (x == m) c++;
}
return c;
}C++
int smallestFreq(const string& w) {
char m = '{';
int c = 0;
for (char x : w) {
if (x < m) { m = x; c = 1; } else if (x == m) c++;
}
return c;
}
vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
vector<int> atLeast(12, 0);
for (const string& w : words) atLeast[smallestFreq(w)]++;
for (int v = 10; v >= 0; v--) atLeast[v] += atLeast[v + 1];
vector<int> res;
for (const string& q : queries) res.push_back(atLeast[smallestFreq(q) + 1]);
return res;
}JavaScript
var numSmallerByFrequency = function(queries, words) {
var f = function(w) {
var m = 200, c = 0;
for (var i = 0; i < w.length; i++) {
var x = w.charCodeAt(i);
if (x < m) { m = x; c = 1; } else if (x === m) c++;
}
return c;
};
var atLeast = [];
for (var k = 0; k < 12; k++) atLeast.push(0);
for (var i = 0; i < words.length; i++) atLeast[f(words[i])]++;
for (var v = 10; v >= 0; v--) atLeast[v] += atLeast[v + 1];
var res = [];
for (var q = 0; q < queries.length; q++) res.push(atLeast[f(queries[q]) + 1]);
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.