The problem Compare Strings by Frequency of the Smallest Character Leetcode Solution, states that we define a function f(s) over a non-empty string s such that f(s) is equal to the frequency of the smallest character in the string. Then we are given some words and some queries. for each query, we are required to find the number of words such that f(words) > f(query_word). Then we have to return the answer for all the queries as a vector or an array. So, before diving deep into the solution, let’s take a look at a few examples.
queries = ["cbd"], words = ["zaaaz"]
[1]
Explanation: f(“zaaaz”) = 3, because the smallest character is ‘a’ that has a frequency equal to 3, while f(“cbd”) = 1. So, we have only a single word that has f(i) > f(query_word).
queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
[1,2]
Explanation: So, after calculation of the value of the defined function for all the given words. We find f(“a”) = 1, f(“aa”) = 2, f(“aaa”) = 3, f(“aaaa”) = 4. After evaluating the value of function for the words given in the queries, we find f(“bbb”) = 3, f(“cc”) = 2. So, then we find that for the word f(“bbb”), we have a single word “aaaa” that has function value greater than 3. Similarly, for the word “cc”, we have words “aaa”, “aaaa” that have greater function value.
Table of Contents
Approach for Compare Strings by Frequency of the Smallest Character Leetcode Solution
The problem Compare Strings by Frequency of the Smallest Character Leetcode Solution asks to find the number of words from the input that have value for a defined function greater than the value of the function for the query words. The function f(s) defined over non-empty strings is equal to the frequency of the smallest character in a string. So, first, we find the value of the function for all the query words. We do the same for all the input words. We also create an extra array that stores the number of words that have function value equal to i. This array will help us find answers for the queries in constant time. Each index i of the array refers to the number of words that have function value = i.
After evaluation of the function value and storing them in our temporary array. We take the suffix sum of the temporary array such that each index now stores the total number of words that have function value greater or equal to i. Now we simply store the answer for each query word in an array or vector and return it.
Code for Compare Strings by Frequency of the Smallest Character Leetcode Solution
C++ code
#include <bits/stdc++.h>
using namespace std;
vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
vector<int> q;
for(auto x: queries){
int f[26] = {0};
int mn = 26;
for(auto y: x){
f[y-'a']++;
mn = min(mn, y-'a');
}
q.push_back(f[mn]);
}
int fr[12];memset(fr, 0, sizeof fr);
for(auto x: words){
int f[26] = {0};
int mn = 26;
for(auto y: x){
f[y-'a']++;
mn = min(mn, y-'a');
}
fr[f[mn]]++;
}
for(int i=9;i>=0;i--)
fr[i] += fr[i+1];
vector<int> ans;
for(auto x: q){
ans.push_back(fr[x+1]);
}
return ans;
}
int main(){
vector<string> queries = {"bbb","cc"};
vector<string> words = {"a","aa","aaa","aaaa"};
vector<int> answer = numSmallerByFrequency(queries, words);
for(auto x: answer)
cout<<x<<" ";
}
1 2
Java Code
import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
public static int[] numSmallerByFrequency(String[] queries, String[] words) {
ArrayList<Integer> q = new ArrayList<Integer>();
for(String x: queries){
int[] f = new int[26];
for(int i=0;i<26;i++)
f[i] = 0;
int mn = 26;
int sz = x.length();
for(int i=0;i<sz;i++){
int y = x.charAt(i);
f[y-'a']++;
mn = Math.min(mn, y-'a');
}
q.add(f[mn]);
}
int[] fr = new int[12];
for(int i=0;i<12;i++)
fr[i] = 0;
for(String x: words){
int[] f = new int[26];
for(int i=0;i<26;i++)
f[i] = 0;
int mn = 26;
int sz = x.length();
for(int i=0;i<sz;i++){
int y = x.charAt(i);
f[y-'a']++;
mn = Math.min(mn, y-'a');
}
fr[f[mn]]++;
}
for(int i=9;i>=0;i--)
fr[i] += fr[i+1];
int[] ans = new int[queries.length];
for(int i=0;i<q.size();i++){
ans[i] = (fr[q.get(i)+1]);
}
return ans;
}
public static void main (String[] args) throws java.lang.Exception
{
String[] queries = {"bbb","cc"};
String[] words = {"a","aa","aaa","aaaa"};
int[] answer = numSmallerByFrequency(queries, words);
for(int x: answer)
System.out.print(x+" ");
}
}1 2
Complexity Analysis
Time Complexity
O(Q + N), since we have to calculate the function value for all the words and the length of the words is also less than or equal to 10. Thus the time complexity is linear.
Space Complexity
O(Q), since we create an array to store the answer and an extra array of size 10 for temporary use. The space complexity is also linear.