Domain 2MediumMEDIUM

Compare Strings by Frequency of the Smallest Character

Precompute the frequency of the smallest character for all words, sort these scores to enable binary searching against query frequencies.

Domain: medium•Updated: 2026-09-09
#binary search#sorting#O(N log M)#string manipulation

Problem Breakdown

We are given two arrays of strings: queries (the questions) and words (the reference set). For each string, we define a function f(s)f(s) which counts the frequency of its lexicographically smallest character.

  • Goal: For every query in queries, count how many words in words have an ff value strictly greater than that specific query’s ff value (f(query)<f(word)f(query) < f(word)).
  • Inputs: Two lists of strings (queries, words). Constraints indicate lengths are small (up to 10) and arrays up to 2000 elements, with lowercase English letters only.
  • Outputs: A list of integers representing the count for each query.

Intuition

  1. Brute Force: For each query qq, iterate through every word ww. Calculate f(q)f(q) and f(w)f(w). If f(q)<f(w)f(q) < f(w), increment a counter for that query.
    • Complexity: Let NN be number of queries, MM words, LL string length. Time is roughly O(N⋅M⋅L)O(N \cdot M \cdot L). With given constraints (20002×10≈4×1072000^2 \times 10 \approx 4 \times 10^7), this might pass but risks TLE in Python due to interpreter overhead on nested loops, and it doesn’t scale if inputs grow.
  2. Optimization: Notice that f(w)f(w) is constant regardless of the query. We can compute all word scores upfront (M⋅LM \cdot L).
  3. Querying Strategy: If we store these precomputed word scores in a sorted list, for any new query score, we only need to find how many stored values are greater than it. This transforms the per-query cost from O(M)O(M) to O(log⁡M)O(\log M).
  4. Further Optimization (Senior Insight): Since string length is capped at 10, the maximum possible frequency is also small (≤10\le 10). We could use a bucket array (frequency map of frequencies) and prefix sums for O(1)O(1) lookup per query after preprocessing. However, sorting + binary search (bisect) is more generic and idiomatic in Python interviews unless strict constant-time queries are required with massive data ranges. I will implement the Sorting approach as it balances readability and performance well within constraints while demonstrating algorithmic thinking about separating computation from comparison.

Approach

  1. Define Helper: Create a function to compute f(s)f(s). We find the smallest character in s (using built-in min) and count its occurrences using .count(). Since strings are short, this is efficient enough (O(L)O(L)).
  2. Precompute Word Scores: Iterate through every word in words, calculate their respective scores using the helper function, and store them in a list called word_scores.
  3. Sort: Sort word_scores in ascending order. This enables binary search operations to quickly determine how many words have a score greater than or equal to (or strictly greater than) our query’s threshold.
  4. Process Queries: For each query string:
    • Calculate its ff value (query_score).
    • Use bisect_right from the standard library on word_scores. This returns an insertion point where all elements to the left are ≤\le query_score.
    • The number of words strictly greater than query_score is simply the total length minus this index.
  5. Return: Collect these counts into a result list and return it.

Complexity Analysis

  • Time Complexity:
    • Calculating scores for all words: O(M⋅L)O(M \cdot L).
    • Sorting word scores: O(Mlog⁡M)O(M \log M).
    • Processing queries: For each of the NN queries, we calculate score (LL) and binary search (log⁡M\log M). Total query time is O(N⋅(L+log⁡M))O(N \cdot (L + \log M)).
    • Overall: O((M+N)L+Nlog⁡M)O((M+N)L + N \log M). Given constraints, this is highly efficient.
  • Space Complexity:
    • We store the scores for all words in a list of size MM. Sorting modifies it in place or uses stack space proportional to recursion depth (iterative sort). The bucket approach would use constant extra space relative to alphabet/length limits. Here, we need storage for word frequencies: O(M)O(M).

Solution

import bisect
from typing import List

class Solution:
    def compareStrings(self, queries: List[str], words: List[str]) -> List[int]:
        # Helper function to calculate f(s)
        def get_f(s):
            if not s: 
                return 0
            
            # Find the lexicographically smallest character efficiently
            min_char = min(s)
            
            # Count occurrences of that specific character
            count = s.count(min_char)
            return count

        # Precompute scores for all words and sort them to enable binary search
        word_scores = []
        for w in words:
            word_scores.append(get_f(w))
        
        word_scores.sort()
        
        answer = []
        
        # Process each query using binary search on the sorted list of word scores
        for q in queries:
            f_q = get_f(q)
            
            # bisect_right returns an insertion point i such that all e in a[:i] <= x 
            # and all e in a[i:] > x.
            # We want count where f(word) > f(query), which corresponds to elements after index i.
            idx = bisect.bisect_right(word_scores, f_q)
            
            answer.append(len(word_scores) - idx)
            
        return answer

# Note: Ensure List is imported from typing if running locally without type hints context