Compare strings by frequency of the smallest character

Array Hash Table String Binary Search Sorting

63.2% acceptance

Feb 25, 2026

752

980

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.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn num_smaller_by_frequency(queries: Vec<String>, words: Vec<String>) -> Vec<i32> {
    let f = |s: &str| -> i32 {
      let min_c = s.bytes().min().unwrap();
      s.bytes().filter(|&c| c == min_c).count() as i32
    };
    let mut word_freqs: Vec<i32> = words.iter().map(|w| f(w)).collect();
    word_freqs.sort();
    queries.iter().map(|q| {
      let fq = f(q);
      let pos = word_freqs.partition_point(|&x| x <= fq);
      (word_freqs.len() - pos) as i32
    }).collect()
  }
}