LeetCode Solutions Blog

Compare Strings by Frequency of the Smallest Character

Number: 1273

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given two string arrays, queries and words, compute f(s) for each string s, where f(s) is defined as the frequency of the lexicographically smallest character in s. For each query string in queries, count how many words in words have f(word) greater than f(query). Return the result as an integer array.

Key Insights

Pre-calculate f(s) for each string by finding its smallest character and counting its occurrence.
Sort the list of f(word) values from the words array.
For each query, determine f(query) and use binary search on the sorted list to count how many f(word) values are greater than f(query).
The precomputation and binary search approach scales well given the constraint sizes.

Space and Time Complexity

Time Complexity: O(m log m + n log m), where m is the length of words and n is the length of queries. Space Complexity: O(m), to store the frequency list for words.

Solution

Create a helper function to compute f(s) by scanning the string to find the smallest character and count its frequency.
Compute and store all f(word) values from the words list.
Sort this list of frequencies.
For each query, compute f(query) and use binary search on the sorted list to find the first index where f(word) > f(query). The count of words with a higher frequency is the difference between the total count and this index.
Return the computed counts for all queries.

Code Solutions

# Function to compute f(s)
def frequency_of_smallest_char(s):
    # Find the lexicographically smallest character in s
    smallest = min(s)
    # Count its occurrences
    return s.count(smallest)

def num_smaller_by_frequency(queries, words):
    # Compute the frequency for each word in words
    word_frequencies = [frequency_of_smallest_char(word) for word in words]
    # Sort frequency values to perform binary search later
    word_frequencies.sort()

    # Function to perform binary search on sorted list 'frequencies'
    def count_greater(freq):
        left, right = 0, len(word_frequencies)
        while left < right:
            mid = (left + right) // 2
            if word_frequencies[mid] <= freq:
                left = mid + 1
            else:
                right = mid
        # All elements from index left to end have frequency > freq
        return len(word_frequencies) - left

    # For each query, compute its frequency and count words with frequency greater than query's frequency
    result = []
    for query in queries:
        query_freq = frequency_of_smallest_char(query)
        result.append(count_greater(query_freq))
    return result

# Example usage
queries = ["cbd"]
words = ["zaaaz"]
print(num_smaller_by_frequency(queries, words))  # Output: [1]