Given an array arr[] of N strings and an integer K, the task is to print K strings which occurred the most number of times in the arr[]. If two or more strings have the same frequency then print the lexicographically smallest string.
Note: The value of K is always less than or equal to the number of distinct elements in the array.
Examples:
Input: str[] = {“neveropen”, “neveropen”, “neveropen”, “article”}, K = 1
Output: “neveropen”
Explanation:
“neveropen” –> 2
“neveropen” –> 1
“article” –> 1
Hence, the most occurring string is “neveropen”Input: str[] = {“car”, “bus”, “car”, “bike”, “car”, “bus”, “bike”, “cycle”}, K = 2
Output : “car”, “bus”
Explanation:
“car” –> 3
“bus” –> 2
“bike” –> 2
“cycle” –> 1
string “car” has highest frequency, string “bus” and “bike” both have second highest frequency, but string “bus” is lexicographically small because it has shorter length.
Approach:
- Count the frequency of each string in the array and store it in a HashMap where the string is the key and frequency as the value.
- Now, sort these keys according to their frequencies in ascending order, this is done to keep keys with the least frequencies at the top.
- The strings with equal frequencies are prioritized alphabetically, i.e., the string which is alphabetically greater has a higher priority.
- Delete the top N – K key-value pairs from the HashMap. By doing this the container is left with K keys with the highest frequencies, in reverse order.
- Print the strings stored in the HashMap.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function that returns list of K// most frequent stringsmap<string, int> Freq;class compare { public: bool operator()(string& a, string& b) { if (a == b) { return Freq[a] > Freq[b]; } return a > b; }};vector<string> frequentWords(vector<string> arr, int K){ // Hash map to store the frequency // of each string map<string, int> Freq; // Set the default frequency of // each string 0 for (auto word : arr) { Freq[word]++; } // Using a priority queue to store // the strings in accordance of the // frequency and alphabetical order // (if frequency is equal) // Lambda expression is used set the // priority, if frequencies are not // equal than the string with greater // frequency is returned else the // string which is lexically smaller // is returned priority_queue<string, vector<string>, compare> Order; // Traverse the HashMap for (auto it : Freq) { Order.push(it.first); // Remove top (N - K) elements if (Order.size() > K) { Order.pop(); } } // Order queue has K most frequent // strings in a reverse order vector<string> ans; while (Order.size()) { ans.push_back(Order.top()); Order.pop(); } // Reverse the ArrayList so as // to get in the desired order reverse(ans.begin(), ans.end()); return ans;}// Driver Codeint main(){ int N = 3, K = 2; // Given array vector<string> arr{ "car", "bus", "car" }; // Function Call vector<string> ans = frequentWords(arr, K); // Print the K most occurring strings for (auto it : ans) { cout << it << endl; }}// This code is contributed by garg28harsh. |
Java
// Java program for the above approachimport java.util.*;class FrequentWords { // Function that returns list of K // most frequent strings public static ArrayList<String> frequentWords(ArrayList<String> arr, int K) { // Hash map to store the frequency // of each string HashMap<String, Integer> Freq = new HashMap<>(); // Set the default frequency of // each string 0 for (String word : arr) { Freq.put(word, Freq.getOrDefault(word, 0) + 1); } // Using a priority queue to store // the strings in accordance of the // frequency and alphabetical order // (if frequency is equal) // Lambda expression is used set the // priority, if frequencies are not // equal than the string with greater // frequency is returned else the // string which is lexically smaller // is returned PriorityQueue<String> Order = new PriorityQueue<>( (a, b) -> (Freq.get(a) != Freq.get(b)) ? Freq.get(a) - Freq.get(b) : b.compareTo(a)); // Traverse the HashMap for (String word : Freq.keySet()) { Order.offer(word); // Remove top (N - K) elements if (Order.size() > K) { Order.poll(); } } // Order queue has K most frequent // strings in a reverse order ArrayList<String> ans = new ArrayList<>(); while (!Order.isEmpty()) { ans.add(Order.poll()); } // Reverse the ArrayList so as // to get in the desired order Collections.reverse(ans); return ans; } // Driver Code public static void main(String[] args) { int N = 3, K = 2; // Given array ArrayList<String> arr = new ArrayList<String>(); arr.add("car"); arr.add("bus"); arr.add("car"); // Function Call ArrayList<String> ans = frequentWords(arr, K); // Print the K most occurring strings for (String word : ans) { System.out.println(word + " "); } }} |
C#
using System;using System.Collections.Generic;using System.Linq;// Class to store the solutionclass Solution{ // Function to return the list of K most frequent words public static IList<string> frequentWords(IList<string> arr, int K) { // Dictionary to store the frequency of each word Dictionary<string, int> Freq = new Dictionary<string, int>(); // Loop through the given list to update the frequency of each word foreach (string word in arr) { if (Freq.ContainsKey(word)) { // Increase the frequency if the word already exists in the dictionary Freq[word]++; } else { // Add the word to the dictionary and set its frequency to 1 Freq[word] = 1; } } // SortedSet to store the words in accordance of the frequency SortedSet<string> Order = new SortedSet<string>(Comparer<string>.Create((a, b) => { // Compare the frequency of two words int freqCompare = Freq[b].CompareTo(Freq[a]); // If the frequencies are equal, compare the words lexically if (freqCompare == 0) { return string.Compare(a, b, StringComparison.Ordinal); } return freqCompare; })); // Loop through the keys of the dictionary to add them to the SortedSet foreach (string word in Freq.Keys) { Order.Add(word); // Remove the last element if the size of the SortedSet exceeds K if (Order.Count > K) { Order.Remove(Order.Last()); } } // Convert the SortedSet to a list and return it return Order.ToList(); } // Driver Code public static void Main(string[] args) { int N = 3, K = 2; List<string> arr = new List<string>() { "car", "bus", "car" }; // Call the function to get the list of K most frequent words List<string> ans = frequentWords(arr, K).ToList(); // Loop through the list and print each word foreach (string word in ans) { Console.WriteLine(word); } }}//This code is contributed by rudra1807raj |
Javascript
// Javascript program for the above approach// Function that returns list of K// most frequent stringsfunction frequentWords(arr, K){ // Hash map to store the frequency // of each string var Freq = new Map(); // Set the default frequency of // each string 0 for (var word of arr) { Freq.set(word, Freq.has(word)?Freq.get(word):0); } // Using a priority queue to store // the strings in accordance of the // frequency and alphabetical order // (if frequency is equal) // Lambda expression is used set the // priority, if frequencies are not // equal than the string with greater // frequency is returned else the // string which is lexically smaller // is returned var Order = []; // Traverse the HashMap for (var word of [...Freq.keys()]) { Order.push(word); // Remove top (N - K) elements if (Order.length > K) { Order.pop(); } } // Order queue has K most frequent // strings in a reverse order var ans = []; Order.sort((a,b)=>a[0]-b[0]); while (Order.length!=0) { ans.push(Order[Order.length-1]) Order.pop(); } // Reverse the ArrayList so as // to get in the desired order ans.reverse(); return ans;}// Driver Codevar N = 3, K = 2;// Given arrayvar arr = [];arr.push("car");arr.push("bus");arr.push("car");// Function Callvar ans = frequentWords(arr, K);// Print the K most occurring stringsfor (var word of ans) { console.log(word);}// This code is contributed by noob2000. |
Python3
#Python code#importing librariesimport collectionsfrom collections import Counter from queue import PriorityQueue#Function that returns list of K most frequent stringsdef frequentWords(arr, K): # Hash map to store the frequency # of each string Freq = Counter(arr) # Using a priority queue to store # the strings in accordance of the # frequency and alphabetical order # (if frequency is equal) Order = PriorityQueue() # Traverse the HashMap for word in Freq: Order.put((-Freq[word], word)) # Remove top (N - K) elements if Order.qsize() > K: Order.get() # Order queue has K most frequent # strings in a reverse order ans = [] while not Order.empty(): ans.append(Order.get()[1]) # Reverse the ArrayList so as # to get in the desired order ans.reverse() return ans# Driver Codeif __name__ == "__main__": N = 3 K = 2 # Given array arr = ["car", "bus", "car"] # Function Call ans = frequentWords(arr, K)[::-1] # Print the K most occurring strings print(*ans, sep="\n") |
Output:
car bus
Time Complexity: O(N*log2N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
