Problem Description

Given two string arrays queries and words, for each string in queries, you need to determine how many strings in words have a higher frequency of their smallest character.

The frequency of the smallest character in a string s, denoted as f(s), is defined as the number of times the smallest (lexicographically) character appears in s. For example, for s = "abbcc", the smallest character is 'a', and f(s) = 1. For s = "aabc", the smallest character is 'a', and f(s) = 2.

For each query string q in queries, compute f(q), and count how many words in words have f(w) > f(q). Return an integer array with the results for each query.

Constraints:

• 1 ≤ queries.length, words.length ≤ 2000
• 1 ≤ queries[i].length, words[i].length ≤ 10
• queries[i] and words[i] consist of lowercase English letters.

Thought Process

At first glance, the problem seems to require comparing every query string against every word string, which hints at a brute-force solution. For each query, we would:

• Compute its smallest character frequency f(q).
• For each word, compute f(w) and compare with f(q) to count how many times f(w) > f(q).

However, this approach would result in a time complexity of O(Q * W), where Q and W are the lengths of queries and words. Given the constraints, this is acceptable, but we can optimize further.

Since the maximum length of any string is 10, the possible values for f(s) are limited (from 1 to 10). This allows us to precompute and sort the frequencies for words to answer each query more efficiently.

Solution Approach

Let's break down the steps to solve the problem efficiently:

1. Compute Frequency: Write a helper function to compute f(s) for any string s by finding the smallest character and counting its occurrences.
2. Preprocess words: For each word in words, compute f(w) and store the frequencies in a list. Then, sort this list. Sorting allows us to quickly count how many frequencies are greater than a given value using binary search.
3. Process Queries: For each query in queries, compute f(q). Use binary search (e.g., bisect_right in Python) to find the first index in the sorted words frequencies where the frequency is greater than f(q). The number of such words is the number of elements to the right of that index.
4. Return Results: Collect the counts for each query in a result list and return it.

This approach leverages precomputation and binary search to reduce the per-query time from O(W) to O(log W).

Example Walkthrough

Let's consider queries = ["bbb", "cc"] and words = ["a", "aa", "aaa", "aaaa"].

• Compute f(w) for each word:
  • "a" → smallest = 'a', count = 1
  • "aa" → smallest = 'a', count = 2
  • "aaa" → smallest = 'a', count = 3
  • "aaaa" → smallest = 'a', count = 4
  So, words_freqs = [1, 2, 3, 4].
• Sort words_freqs: already sorted.
• For "bbb": smallest = 'b', count = 3. So f("bbb") = 3.
  • How many words_freqs are greater than 3? Only 4.
  • So, answer is 1.
• For "cc": smallest = 'c', count = 2. So f("cc") = 2.
  • How many words_freqs are greater than 2? 3 and 4.
  • So, answer is 2.
• Final answer: [1, 2]

Time and Space Complexity

• Brute-force: For each query, compare with every word. O(Q * W), where Q = number of queries, W = number of words.
• Optimized:
  • Preprocessing words: O(W log W) for sorting, O(W * L) for computing frequencies (L = max string length, here at most 10).
  • Each query: O(log W) for binary search + O(L) for computing f(q).
  • Total: O(W log W + Q log W)
  • Space: O(W) for the frequencies list.
• The optimization is possible because the possible frequency values are small and the number of queries and words is moderate.

Summary

The key to solving "Compare Strings by Frequency of the Smallest Character" efficiently is precomputing and sorting the frequencies of words, then using binary search for each query. This reduces the time complexity per query from linear to logarithmic. The approach is both elegant and practical, leveraging the small input limits and properties of the problem to avoid unnecessary repeated computation.

Code Implementation

from bisect import bisect_right

def f(s):
    return s.count(min(s))

def numSmallerByFrequency(queries, words):
    words_freqs = sorted([f(w) for w in words])
    res = []
    for q in queries:
        fq = f(q)
        # Find how many in words_freqs are greater than fq
        idx = bisect_right(words_freqs, fq)
        res.append(len(words_freqs) - idx)
    return res
      

#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int f(const string& s) {
    char min_c = *min_element(s.begin(), s.end());
    int count = 0;
    for (char c : s) {
        if (c == min_c) count++;
    }
    return count;
}

vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
    vector<int> words_freqs;
    for (const string& w : words) {
        words_freqs.push_back(f(w));
    }
    sort(words_freqs.begin(), words_freqs.end());
    vector<int> res;
    for (const string& q : queries) {
        int fq = f(q);
        int idx = upper_bound(words_freqs.begin(), words_freqs.end(), fq) - words_freqs.begin();
        res.push_back(words_freqs.size() - idx);
    }
    return res;
}
      

import java.util.*;

public class Solution {
    private int f(String s) {
        char min = 'z';
        int count = 0;
        for (char c : s.toCharArray()) {
            if (c < min) {
                min = c;
                count = 1;
            } else if (c == min) {
                count++;
            }
        }
        return count;
    }

    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] wordsFreqs = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            wordsFreqs[i] = f(words[i]);
        }
        Arrays.sort(wordsFreqs);
        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int fq = f(queries[i]);
            int idx = upperBound(wordsFreqs, fq);
            res[i] = wordsFreqs.length - idx;
        }
        return res;
    }

    // Find the first index where wordsFreqs[idx] > val
    private int upperBound(int[] arr, int val) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] <= val) left = mid + 1;
            else right = mid;
        }
        return left;
    }
}
      

function f(s) {
    let minChar = 'z';
    let count = 0;
    for (let c of s) {
        if (c < minChar) {
            minChar = c;
            count = 1;
        } else if (c === minChar) {
            count++;
        }
    }
    return count;
}

function numSmallerByFrequency(queries, words) {
    let wordsFreqs = words.map(f).sort((a, b) => a - b);
    let res = [];
    for (let q of queries) {
        let fq = f(q);
        // Binary search for first index with value > fq
        let left = 0, right = wordsFreqs.length;
        while (left < right) {
            let mid = Math.floor((left + right) / 2);
            if (wordsFreqs[mid] <= fq) left = mid + 1;
            else right = mid;
        }
        res.push(wordsFreqs.length - left);
    }
    return res;
}