Compare Strings by Frequency of the Smallest Character

Medium
1213.

Compare Strings by Frequency of the Smallest Character

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.

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 <= 2000
  • 1 <= words.length <= 2000
  • 1 <= queries[i].length, words[i].length <= 10
  • queries[i] and words[i] consist of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} queries
 * @param {string[]} words
 * @return {number[]}
 */
var numSmallerByFrequency = function(queries, words) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 2000
  • 1 <= words.length <= 2000
  • 1 <= queries[i].length, words[i].length <= 10
  • queries[i] and words[i] consist of lowercase English letters

Hints for Compare Strings by Frequency of the Smallest Character

  1. Hint 1

    Computing f takes one pass: track the smallest letter so far and how often it has appeared.

  2. Hint 2

    Since every word has length at most 10, f is between 1 and 10 — bucket the words by their f value.

  3. Hint 3

    A suffix sum over the buckets answers "how many words have f greater 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

  1. Compute f(w) for each word in one pass per word and increment bucket[f(w)].
  2. Turn the buckets into suffix sums: atLeast[v] = Σ_{u ≥ v} bucket[u] for v from 10 down to 1 (with atLeast[11] = 0).
  3. For each query q, the answer is atLeast[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

  • f counts the smallest letter, not the most frequent one.
  • The comparison is strict: words with equal f are not counted.
  • Recomputing f for 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.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings