Compare Strings by Frequency of the Smallest Character

MEDIUM

Description

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 i^th query.

Example 1:

Input: queries = ["cbd"], words = ["zaaaz"]
Output: [1]
Explanation: On the first query we have f("cbd") = 1, f("zaaaz") = 3 so f("cbd") < f("zaaaz").

Example 2:

Input: queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
Output: [1,2]
Explanation: On the first query only f("bbb") < f("aaaa"). On the second query both f("aaa") and f("aaaa") are both > f("cc").

Constraints:

1 <= queries.length <= 2000
1 <= words.length <= 2000
1 <= queries[i].length, words[i].length <= 10
queries[i][j], words[i][j] consist of lowercase English letters.

Approaches

Checkout 3 different approaches to solve Compare Strings by Frequency of the Smallest Character. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

This approach directly translates the problem statement into code. For each query string, we iterate through all the words in the words array. In each inner iteration, we calculate the frequency of the smallest character for both the query string and the current word string and compare them.

Algorithm

Initialize an integer array answer of the same size as queries.
Define a helper function f(s) that calculates the frequency of the smallest character in s.
Loop through each query at index i from 0 to queries.length - 1.
Calculate queryFreq = f(queries[i]).
Initialize a counter count = 0.
Loop through each word in the words array.
Calculate wordFreq = f(word).
If queryFreq < wordFreq, increment count.
After the inner loop finishes, set answer[i] = count.
Return answer.

We'll need a helper function, let's call it f(s), that takes a string s and returns the frequency of its lexicographically smallest character. To implement f(s), we can use a frequency map (an array of size 26 for lowercase English letters). We iterate through the string s to populate this map. Then, we iterate through the map from index 0 to 25 (representing 'a' to 'z') and return the first non-zero frequency we find.

The main function will iterate through each query in the queries array. For each query, we first calculate its frequency, f(query). Then, we start a nested loop to iterate through every word in the words array. Inside the nested loop, we calculate f(word). If f(query) < f(word), we increment a counter for the current query. After checking all words, the value of the counter is the result for the current query, which we store in our answer array. This process is repeated for all queries.

class Solution {
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] answer = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int queryFreq = f(queries[i]);
            int count = 0;
            for (String word : words) {
                if (queryFreq < f(word)) {
                    count++;
                }
            }
            answer[i] = count;
        }
        return answer;
    }

    private int f(String s) {
        int[] counts = new int[26];
        for (char c : s.toCharArray()) {
            counts[c - 'a']++;
        }
        for (int count : counts) {
            if (count > 0) {
                return count;
            }
        }
        return 0;
    }
}

Complexity Analysis

Time Complexity: O(M * N * L), where `M` is the number of queries, `N` is the number of words, and `L` is the maximum length of a string. For each of the `M` queries, we iterate through `N` words, and for each pair, we call the `f` function which takes O(L) time.Space Complexity: O(M) for the output array. If we exclude the output array, the auxiliary space is O(1) (the frequency map in `f` has a constant size of 26).

Pros and Cons

Pros:

Simple to understand and implement.

Cons:

Inefficient due to redundant calculations. The f(word) is recalculated for every query, leading to a high time complexity.

Code Solutions

Checking out 3 solutions in different languages for Compare Strings by Frequency of the Smallest Character. Click on different languages to view the code.

class Solution { public int [] numSmallerByFrequency ( String [] queries , String [] words ) { int n = words . length ; int [] nums = new int [ n ]; for ( int i = 0 ; i < n ; ++ i ) { nums [ i ] = f ( words [ i ]); } Arrays . sort ( nums ); int m = queries . length ; int [] ans = new int [ m ]; for ( int i = 0 ; i < m ; ++ i ) { int x = f ( queries [ i ]); int l = 0 , r = n ; while ( l < r ) { int mid = ( l + r ) >> 1 ; if ( nums [ mid ] > x ) { r = mid ; } else { l = mid + 1 ; } } ans [ i ] = n - l ; } return ans ; } private int f ( String s ) { int [] cnt = new int [ 26 ]; for ( int i = 0 ; i < s . length (); ++ i ) { ++ cnt [ s . charAt ( i ) - 'a' ]; } for ( int x : cnt ) { if ( x > 0 ) { return x ; } } return 0 ; } }

Video Solution

Watch the video walkthrough for Compare Strings by Frequency of the Smallest Character

Algorithms:

Binary SearchSorting

Data Structures:

ArrayHash TableString