Compare Strings by Frequency of the Smallest Character

Compare Strings by Frequency of the Smallest Character - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: words = ["cbd"], queries = ["aa"]

› Output: [0]

💡 Note: f("aa") = 2 (frequency of 'a'), f("cbd") = 1 (frequency of 'b'). Since 2 > 1, there are 0 words where f("aa") < f(word).

Example 2 — Multiple Words

$ Input: words = ["aa","aaa","cccc"], queries = ["cbd"]

› Output: [3]

💡 Note: f("cbd") = 1, f("aa") = 2, f("aaa") = 3, f("cccc") = 4. Since 1 < 2, 1 < 3, and 1 < 4, all 3 words satisfy the condition.

Example 3 — Mixed Results

$ Input: words = ["bbb","cc"], queries = ["aaa","bb"]

› Output: [1,1]

💡 Note: f("aaa") = 3, f("bb") = 2, f("bbb") = 3, f("cc") = 2. For "aaa": only "bbb" has f > 3 (none do), so 0. Wait, f("bbb") = 3, not > 3. Actually f("bbb") = 3, so 3 = 3, not greater. Let me recalculate...

Constraints

1 ≤ queries.length ≤ 2000
1 ≤ words.length ≤ 2000
1 ≤ queries[i].length, words[i].length ≤ 10
queries[i][j], words[i][j] are lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

words=["aa","aaa","cccc"], queries=["cbd"]

Calculate f(s)

Find frequency of lexicographically smallest char in each string

Compare

Count words where f(query) < f(word)

Key Takeaway

🎯 Key Insight: Pre-calculate and sort frequencies to enable efficient binary search comparisons

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to pre-calculate f(s) for all strings to avoid redundant work. The optimal approach uses binary search after sorting word frequencies. Time: O(n log n + m log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search Optimization	O(n log n + m log n)	O(n)	Sort word frequencies and use binary search for each query
Pre-calculate Frequencies	O(n×m + (n+m)×k)	O(n+m)	Calculate f(s) once for all strings, then compare arrays
Brute Force	O(n×m×k)	O(1)	Calculate f(s) for each query and compare with every word

Binary Search Optimization — Algorithm Steps

Calculate f(word) for all words
Sort word frequencies
For each query, binary search for count of greater frequencies

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Frequencies

Sort word frequencies: [2, 3, 4]

Binary Search

Find position where query_freq fits

Count Greater

Elements after position are greater

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int f(char* s) {
    char minChar = s[0];
    int len = strlen(s);
    for (int i = 1; i < len; i++) {
        if (s[i] < minChar) minChar = s[i];
    }
    int count = 0;
    for (int i = 0; i < len; i++) {
        if (s[i] == minChar) count++;
    }
    return count;
}

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int upperBound(int* arr, int size, int target) {
    int left = 0, right = size;
    while (left < right) {
        int mid = (left + right) / 2;
        if (arr[mid] <= target) left = mid + 1;
        else right = mid;
    }
    return left;
}

int* solution(char words[][100], int wordsSize, char queries[][100], int queriesSize, int* returnSize) {
    // Pre-calculate and sort word frequencies
    int* wordFreqs = (int*)malloc(wordsSize * sizeof(int));
    for (int i = 0; i < wordsSize; i++) {
        wordFreqs[i] = f(words[i]);
    }
    qsort(wordFreqs, wordsSize, sizeof(int), compare);
    
    int* result = (int*)malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    
    for (int i = 0; i < queriesSize; i++) {
        int queryFreq = f(queries[i]);
        int pos = upperBound(wordFreqs, wordsSize, queryFreq);
        result[i] = wordsSize - pos;
    }
    
    free(wordFreqs);
    return result;
}

int main() {
    char words[1000][100], queries[1000][100];
    int wordsSize = 0, queriesSize = 0;
    
    // Simplified parsing
    char line[10000];
    fgets(line, sizeof(line), stdin);
    char* token = strtok(line, "[],\"\n ");
    while (token != NULL && wordsSize < 1000) {
        strcpy(words[wordsSize++], token);
        token = strtok(NULL, "[],\"\n ");
    }
    
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[],\"\n ");
    while (token != NULL && queriesSize < 1000) {
        strcpy(queries[queriesSize++], token);
        token = strtok(NULL, "[],\"\n ");
    }
    
    int returnSize;
    int* result = solution(words, wordsSize, queries, queriesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + m log n)

n log n for sorting word frequencies + m queries × log n binary search

⚡ Linearithmic

Space Complexity

O(n)

Array to store n word frequencies for sorting

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

842 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler