Given two array of strings, arr1[] and arr2[], the task is to count the number of strings in arr2[] whose frequency of the smallest characters is less than the frequency of the smallest character for each string in arr1[].
Examples:
Input: arr1[] = {“cbd”}, arr2[] = {“zaaaz”}
Output: 1
Explanation:
The frequency of the smallest characters in “cbd” is 1 which is less than the frequency of the smallest characters in “zaaaz” which is 2.
Therefore, the total count is 1 for the string “cbd”.Input: arr1[] = {“yyy”,”zz”}, arr2[] = {“x”,”xx”,”xxx”,”xxxx”}
Output: 1 2
Explanation:
1. The frequency of the smallest characters in “yyy” is 3 which is less than the frequency of the smallest characters in “xxxx” which is 4.
Therefore, the total count is 1 for the string “yyy”.
2. The frequency of the smallest characters in “zz” is 2 which is less than the frequency of the smallest characters in “xxx” and “xxxx” which is 3 and 4 respectively.
Therefore, the total count is 2 for the string “zz”.
Approach: This problem can be solved using Greedy Approach. Below are the steps:
- For each string in the array, arr2[] count the frequency of the smallest characters and store it in the array (say freq[]).
- Sort the frequency array freq[].
- Now, for each string in the array arr1[] count the frequency of smallest characters in the string (say X).
- For each X, find the number of elements greater than X in freq[] using Binary Search by using the approach discussed this article.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count the frequency of // minimum character int countMinFreq(string s) { // Sort the string s sort(s.begin(), s.end()); // Return the count with smallest // character return count(s.begin(), s.end(), s[0]); } // Function to count number of frequency // of smallest character of string arr1[] // is less than the string in arr2[] void countLessThan(vector<string>& arr1, vector<string>& arr2) { // To store the frequency of smallest // character in each string of arr2 vector< int > freq; // Traverse the arr2[] for (string s : arr2) { // Count the frequency of smallest // character in string s int f = countMinFreq(s); // Append the frequency to freq[] freq.push_back(f); } // Sort the frequency array sort(freq.begin(), freq.end()); // Traverse the array arr1[] for (string s : arr1) { // Count the frequency of smallest // character in string s int f = countMinFreq(s); // find the element greater than f auto it = upper_bound(freq.begin(), freq.end(), f); // Find the count such that // arr1[i] < arr2[j] int cnt = freq.size() - (it - freq.begin()); // Print the count cout << cnt << ' ' ; } } // Driver Code int main() { vector<string> arr1, arr2; arr1 = { "yyy" , "zz" }; arr2 = { "x" , "xx" , "xxx" , "xxxx" }; // Function Call countLessThan(arr1, arr2); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { // Function to count the frequency of // minimum character static int countMinFreq(String s) { // Sort the string s char [] tempArray = s.toCharArray(); Arrays.sort(tempArray); s = new String(tempArray); // Return the count with smallest // character int x = 0 ; for ( int i = 0 ; i < s.length(); i++) if (s.charAt(i) == s.charAt( 0 )) x++; return x; } // Function to count number of frequency // of smallest character of string arr1[] // is less than the string in arr2[] static void countLessThan(List<String> arr1, List<String> arr2) { // To store the frequency of smallest // character in each string of arr2 List<Integer> freq = new ArrayList<Integer>(); // Traverse the arr2[] for (String s : arr2) { // Count the frequency of smallest // character in string s int f = countMinFreq(s); // Append the frequency to freq[] freq.add(f); } // Sort the frequency array Collections.sort(freq); // Traverse the array arr1[] for (String s : arr1) { // Count the frequency of smallest // character in string s int f = countMinFreq(s); // find the element greater than f int it = upper_bound(freq, f); // Find the count such that // arr1[i] < arr2[j] int cnt = freq.size() - it; // Print the count System.out.print(cnt + " " ); } } static int upper_bound(List<Integer> freq, int f) { int low = 0 , high = freq.size() - 1 ; while (low < high) { int mid = (low + high) / 2 ; if (freq.get(mid) > f) high = mid; else low = mid + 1 ; } return (freq.get(low) < f) ? low++ : low; } // Driver Code public static void main(String[] args) { List<String> arr1, arr2; arr1 = Arrays.asList( new String[] { "yyy" , "zz" }); arr2 = Arrays.asList( new String[] { "x" , "xx" , "xxx" , "xxxx" }); // Function Call countLessThan(arr1, arr2); } } // This code is contributed by jithin. |
Python3
# Python3 program for the above approach from bisect import bisect_right as upper_bound # Function to count the frequency # of minimum character def countMinFreq(s): # Sort the string s s = sorted (s) # Return the count with smallest # character x = 0 for i in s: if i = = s[ 0 ]: x + = 1 return x # Function to count number of frequency # of smallest character of string arr1[] # is less than the string in arr2[] def countLessThan(arr1, arr2): # To store the frequency of smallest # character in each string of arr2 freq = [] # Traverse the arr2[] for s in arr2: # Count the frequency of smallest # character in string s f = countMinFreq(s) # Append the frequency to freq[] freq.append(f) # Sort the frequency array feq = sorted (freq) # Traverse the array arr1[] for s in arr1: # Count the frequency of smallest # character in string s f = countMinFreq(s); # find the element greater than f it = upper_bound(freq,f) # Find the count such that # arr1[i] < arr2[j] cnt = len (freq) - it # Print the count print (cnt, end = " " ) # Driver Code if __name__ = = '__main__' : arr1 = [ "yyy" , "zz" ] arr2 = [ "x" , "xx" , "xxx" , "xxxx" ] # Function Call countLessThan(arr1, arr2); # This code is contributed by Mohit Kumar |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to count the frequency of // minimum character static int countMinFreq(String s) { // Sort the string s char [] tempArray = s.ToCharArray(); Array.Sort(tempArray); s = new string (tempArray); // Return the count with smallest // character int x = 0; for ( int i = 0; i < s.Length; i++) if (s[i] == s[0]) x++; return x; } // Function to count number of frequency // of smallest character of string arr1[] // is less than the string in arr2[] static void countLessThan(List< string > arr1, List< string > arr2) { // To store the frequency of smallest // character in each string of arr2 List< int > freq = new List< int >(); // Traverse the arr2[] foreach ( string s in arr2) { // Count the frequency of smallest // character in string s int f = countMinFreq(s); // Append the frequency to freq[] freq.Add(f); } // Sort the frequency array freq.Sort(); // Traverse the array arr1[] foreach ( string s in arr1) { // Count the frequency of smallest // character in string s int f = countMinFreq(s); // find the element greater than f int it = upper_bound(freq, f); // Find the count such that // arr1[i] < arr2[j] int cnt = freq.Count - it; // Print the count Console.Write(cnt + " " ); } } static int upper_bound(List< int > freq, int f) { int low = 0, high = freq.Count - 1; while (low < high) { int mid = (low + high) / 2; if (freq[mid] > f) high = mid; else low = mid + 1; } return (freq[low] < f) ? low++ : low; } // Driver Code public static void Main( string [] args) { List< string > arr1 = new List< string >(); List< string > arr2 = new List< string >(); arr1.Add( "yyy" ); arr1.Add( "zz" ); arr2.Add( "x" ); arr2.Add( "xx" ); arr2.Add( "xxx" ); arr2.Add( "xxxx" ); // Function Call countLessThan(arr1, arr2); } } // This code is contributed by phasing17. |
Javascript
<script> // JS program for the above approach function upper_bound(freq, f) { let low = 0, high = freq.length - 1; while (low < high) { let mid = Math.floor((low + high) / 2); if (freq[mid] > f) high = mid; else low = mid + 1; } return (freq[low] < f) ? low++ : low; } // Function to count the frequency of // minimum character function countMinFreq(s) { // Sort the string s s = s.split( '' ).sort().join( '' ); // Return the count with smallest // character let x = 0; for (let i=0;i<s.length;i++){ if (s[i] == s[0]) x += 1; } return x; } // Function to count number of frequency // of smallest character of string arr1[] // is less than the string in arr2[] function countLessThan(arr1,arr2) { // To store the frequency of smallest // character in each string of arr2 let freq = []; // Traverse the arr2[] for (let i = 0;i< arr2.length;i++) { // Count the frequency of smallest // character in string s let f = countMinFreq(arr2[i]); // Append the frequency to freq[] freq.push(f); } // Sort the frequency array freq= freq.sort( function (a,b){ return a-b}); // Traverse the array arr1[] for (let i = 0;i< arr1.length;i++) { // Count the frequency of smallest // character in string s let f = countMinFreq(arr1[i]); // find the element greater than f let it = upper_bound(freq, f); // Find the count such that // arr1[i] < arr2[j] let cnt = freq.length - (it); // Print the count document.write(cnt, ' ' ); } } // Driver Code let arr1, arr2; arr1 = [ "yyy" , "zz" ]; arr2 = [ "x" , "xx" , "xxx" , "xxxx" ]; // Function Call countLessThan(arr1, arr2); </script> |
1 2
Time Complexity: O(N + M*log M), where N and M are the lengths of given arrays respectively.
Auxiliary Space: O(M)
Efficient Approach:
In this approach, we will use the concept of count sort, to avoid sorting the array. Below are the steps:
- Create a utility function, which calculates the frequency of the smallest character in the string i.e. getF(s).
- Initialize a freq array, of MAX_CHAR + 1, size. This array stores the count of the frequency of the smallest character in the string. For example, if two strings in words array, have smallest character count equals 5, then, freq[5] = 2.
- Now, calculate the cummulative frequency for the freq array. This is done because for query[i], we need to tell the number of strings in the words array, that has smallest character count greater than the smallest character count of query[i].
- At last, traverse the queries array, and freq[getF(queries[i]) + 1], will be the answer for each query.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // considering maximum number of characters in each string of words or queries array is 11. const int MAX_CHAR = 11; // Function to count the frequency of // minimum character int getF(string &s) { // Return the count with smallest // character return count(s.begin(), s.end(), *min_element(s.begin(), s.end())); } // Function to count number of frequency // of smallest character of string arr1[] // is less than the string in arr2[] void numSmallerByFrequency(vector<string>& queries, vector<string>& words) { // creating a frequency array vector< int > freq(MAX_CHAR + 1, 0); // calculating the freq of the smallest character count of each string for ( int i = 0; i < words.size(); i++){ int currFreq = getF(words[i]); freq[currFreq]++; } //Find cumulative frequency // because question asks for freq of smallest character count of each string in words array // should be greater than the freq of smallest character count of each string, for queries[i] for ( int i = MAX_CHAR - 2; i >= 0; i--){ freq[i] = freq[i] + freq[i+1]; } // now, for each queries[i], freq[getF(queries[i]) + 1] is the answer for ( int i = 0; i < queries.size(); i++){ int currFreq = getF(queries[i]); cout << freq[currFreq + 1] << " " ; } } // Driver Code int main() { vector<string> arr1, arr2; arr1 = { "yyy" , "zz" }; arr2 = { "x" , "xx" , "xxx" , "xxxx" }; // Function Call numSmallerByFrequency(arr1, arr2); return 0; } |
Java
import java.util.*; class Main { // Function to count the frequency of // minimum character public static int getF(String s) { int minCharCount = Collections.frequency(Arrays.asList( s.split( "" )), Collections.min(Arrays.asList(s.split( "" )))); // Return the count with smallest // character return minCharCount; } // Function to count number of frequency // of smallest character of string arr1[] // is less than the string in arr2[] public static void numSmallerByFrequency(List<String> queries, List<String> words) { // considering maximum number of // characters in each string of words or queries array is 11. int MAX_CHAR = 11 ; // creating a frequency array int [] freq = new int [MAX_CHAR + 1 ]; // calculating the freq of the smallest character count of each string for (String word : words) { int currFreq = getF(word); freq[currFreq]++; } // Find cumulative frequency // because question asks for freq of smallest // character count of each string in words array // should be greater than the freq of smallest // character count of each string, for queries[i] for ( int i = MAX_CHAR - 2 ; i >= 0 ; i--) { freq[i] = freq[i] + freq[i + 1 ]; } // now, for each queries[i], freq[getF(queries[i]) + 1] is the answer for (String query : queries) { int currFreq = getF(query); System.out.print(freq[currFreq + 1 ] + " " ); } } // Driver Code public static void main(String[] args) { List<String> arr1 = new ArrayList<>(Arrays.asList( "yyy" , "zz" )); List<String> arr2 = new ArrayList<>(Arrays.asList( "x" , "xx" , "xxx" , "xxxx" )); numSmallerByFrequency(arr1, arr2); } } |
Python3
def getF(s): # Return the count with the smallest character return s.count( min (s, key = s.count)) def num_smaller_by_frequency(queries, words): # Considering the maximum number of characters in each string of words or queries array is 11 MAX_CHAR = 11 # Creating a frequency array freq = [ 0 ] * (MAX_CHAR + 1 ) # Calculating the frequency of the smallest character count of each string for word in words: curr_freq = getF(word) freq[curr_freq] + = 1 # Find cumulative frequency for i in range (MAX_CHAR - 2 , - 1 , - 1 ): freq[i] = freq[i] + freq[i + 1 ] # For each query, freq[getF(query) + 1] is the answer for query in queries: curr_freq = getF(query) print (freq[curr_freq + 1 ], end = " " ) # Driver Code if __name__ = = "__main__" : arr1 = [ "yyy" , "zz" ] arr2 = [ "x" , "xx" , "xxx" , "xxxx" ] # Function Call num_smaller_by_frequency(arr1, arr2) |
C#
using System; using System.Collections.Generic; using System.Linq; class GFG { // considering maximum number of characters in each // string of words or queries array is 11. const int MAX_CHAR = 11; // Function to count the frequency of minimum character static int GetF( string s) { // Return the count with smallest character return s.Count(c => c == s.Min()); } // Function to count number of frequency of smallest // character of string arr1[] is less than the string in // arr2[] static void NumSmallerByFrequency(List< string > queries, List< string > words) { // creating a frequency array int [] freq = new int [MAX_CHAR + 1]; // calculating the freq of the smallest character // count of each string foreach ( string word in words) { int currFreq = GetF(word); freq[currFreq]++; } // Find cumulative frequency // because the question asks for freq of the // smallest character count of each string in words // array should be greater than the freq of the // smallest character count of each string, for // queries[i] for ( int i = MAX_CHAR - 2; i >= 0; i--) { freq[i] = freq[i] + freq[i + 1]; } // now, for each queries[i], freq[GetF(queries[i]) + // 1] is the answer foreach ( string query in queries) { int currFreq = GetF(query); Console.Write(freq[currFreq + 1] + " " ); } } public static void Main( string [] args) { List< string > arr1, arr2; arr1 = new List< string >{ "yyy" , "zz" }; arr2 = new List< string >{ "x" , "xx" , "xxx" , "xxxx" }; // Function Call NumSmallerByFrequency(arr1, arr2); } } // by phasing17 |
Javascript
// Function to count the frequency of the minimum character function getF(s) { // Return the count with the smallest character let minChar = Math.min(...s.split( '' ).map(c => c.charCodeAt())); return s.split( '' ).filter(c => c.charCodeAt() === minChar).length; } // Function to count the number of frequencies // of the smallest character of each string in arr1[] // that is less than the frequency of the smallest character of each string in arr2[] function numSmallerByFrequency(queries, words) { // Creating a frequency array let freq = new Array(MAX_CHAR + 1).fill(0); // Calculating the frequency of the smallest character count of each string words.forEach(word => { let currFreq = getF(word); freq[currFreq]++; }); // Find cumulative frequency // because the question asks for the frequency of the smallest character count // of each string in words array should be greater than the frequency of the smallest character count // of each string for queries[i] for (let i = MAX_CHAR - 2; i >= 0; i--) { freq[i] = freq[i] + freq[i + 1]; } // Now, for each queries[i], freq[getF(queries[i])] is the answer queries.forEach(query => { let currFreq = getF(query); console.log(freq[currFreq + 1] + ' ' ); }); } // Considering the maximum number of characters in each string of words or queries array is 11. const MAX_CHAR = 11; // Driver Code let arr1 = [ "yyy" , "zz" ]; let arr2 = [ "x" , "xx" , "xxx" , "xxxx" ]; // Function Call numSmallerByFrequency(arr1, arr2); |
1 2
Time Complexity: O(N + M), where N and M are the lengths of given arrays respectively.
Auxiliary Space: O(maximum number of characters in words and queries array)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!