Scale Engineer

Compare Strings by Frequency of the Smallest Character

Med
#1098Time: 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: 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).
Algorithms
Binary SearchSorting
Data structures
ArrayHash TableString

Prompt

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.

 

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

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

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).

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem