Given a string array arr[] as input, the task is to print the words sorted by number of distinct characters that occur in the word, followed by length of word.
Note:
- If two words have same number of distinct characters, the word with more total characters comes first.
- If two words have same number of distinct characters and same length, the word that occurs earlier in the sentence must be printed first.
Examples:
Input: arr[] = {“Bananas”, “do”, “not”, “grow”, “in”, “Mississippi”}
Output: do in not Mississippi Bananas grow
Explanation:
After sorting by the number of unique characters and the length the output will be, do in not Mississippi Bananas grow.Input: arr[] = {“thank”, “you”, “neveropen”, “world”}
Output: you neveropen thank world
Explanation:
After sorting by the number of unique characters and the length the output will be, you neveropen thank world.
Approach: The idea is to use Sorting.
- Initialize a map data structure to count all the possible distinct characters from each string of the given array.
- Then sort the array by passing the comparator function, where sorting is done by the number of unique character in word and length of word.
- After sorting is done, print the strings of the array.
For example s = “Bananas do not grow in Mississippi”
Word Number of unique character Length of Word
do 2 2
in 2 2
not 3 3
Bananas 4 7
grow 4 4
Mississippi 4 11
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to return no of// unique character in a wordint countDistinct(string s){ // Initialize map unordered_map<char, int> m; for (int i = 0; i < s.length(); i++) { // Count distinct characters m[s[i]]++; } return m.size();}// Function to perform sortingbool compare(string& s1, string& s2){ if (countDistinct(s1) == countDistinct(s2)) { // Check if size of string 1 // is same as string 2 then // return false because s1 should // not be placed before s2 if (s1.size() == s2.size()) { return false; } return s1.size() > s2.size(); } return countDistinct(s1) < countDistinct(s2);}// Function to print the sorted array of stringvoid printArraystring(string str[], int n){ for (int i = 0; i < n; i++) cout << str[i] << " ";}// Driver Codeint main(){ string arr[] = { "Bananas", "do", "not", "grow", "in", "Mississippi" }; int n = sizeof(arr) / sizeof(arr[0]); // Function call sort(arr, arr + n, compare); // Print result printArraystring(arr, n); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to return no of// unique character in a wordstatic int countDistinct(String s){ // Initialize map Map<Character, Integer> m = new HashMap<>(); for(int i = 0; i < s.length(); i++) { // Count distinct characters if (m.containsKey(s.charAt(i))) { m.put(s.charAt(i), m.get(s.charAt(i)) + 1); } else { m.put(s.charAt(i), 1); } } return m.size();}// Function to print the sorted // array of stringstatic void printArraystring(String[] str, int n){ for(int i = 0; i < n; i++) { System.out.print(str[i] + " "); }}// Driver codepublic static void main(String[] args){ String[] arr = { "Bananas", "do", "not", "grow", "in", "Mississippi" }; int n = arr.length; // Function call Arrays.sort(arr, new Comparator<String>() { public int compare(String a, String b) { if (countDistinct(a) == countDistinct(b)) { // Check if size of string 1 // is same as string 2 then // return false because s1 should // not be placed before s2 return (b.length() - a.length()); } else { return (countDistinct(a) - countDistinct(b)); } } }); // Print result printArraystring(arr, n);}}// This code is contributed by offbeat |
Python3
# Python3 program of the above approach import functools# Function to return no of # unique character in a word def countDistinct(s): # Initialize dictionary m = {} for i in range(len(s)): # Count distinct characters if s[i] not in m: m[s[i]] = 1 else: m[s[i]] += 1 return len(m)# Function to perform sortingdef compare(a, b): if (countDistinct(a) == countDistinct(b)): # Check if size of string 1 # is same as string 2 then # return false because s1 should # not be placed before s2 return (len(b) - len(a)) else: return (countDistinct(a) - countDistinct(b))# Driver Codearr = [ "Bananas", "do", "not", "grow", "in","Mississippi" ]n = len(arr)# Print resultprint(*sorted( arr, key = functools.cmp_to_key(compare)), sep = ' ')# This code is contributed by avanitrachhadiya2155 |
C#
// C# program of the above approach using System; using System.Collections; using System.Collections.Generic; class GFG{ // Function to return no of // unique character in a word static int countDistinct(string s) { // Initialize map Dictionary<char, int> m = new Dictionary<char, int>(); for(int i = 0; i < s.Length; i++) { // Count distinct characters if (m.ContainsKey(s[i])) { m[s[i]]++; } else { m[s[i]] = 1; } } return m.Count; } static int compare(string s1, string s2) { if (countDistinct(s1) == countDistinct(s2)) { // Check if size of string 1 // is same as string 2 then // return false because s1 should // not be placed before s2 return s2.Length - s1.Length; } else { return (countDistinct(s1) - countDistinct(s2)); } } // Function to print the sorted array of string static void printArraystring(string []str, int n) { for(int i = 0; i < n; i++) { Console.Write(str[i] + " "); } } // Driver Code public static void Main(string[] args) { string []arr = { "Bananas", "do", "not", "grow", "in", "Mississippi" }; int n = arr.Length; // Function call Array.Sort(arr, compare); // Print result printArraystring(arr, n); } } // This code is contributed by rutvik_56 |
Javascript
// Javascript program for above approach// function to return number of// unique character in a wordfunction countDistinct(string){ // Initialize map let obj = {}; for(let i = 0; i < string.length; i++){ // count distinct characters if(string[i] in obj){ obj[string[i]] += 1; } else{ obj[string[i]] = 1; } } let cnt = 0; for(ele in obj) cnt++; return cnt;}// Function to perform sortingfunction compare(s1, s2){ if(countDistinct(s1) == countDistinct(s2)){ return (s2.length-s1.length); } else{ return (countDistinct(s1) - countDistinct(s2)); }}// Function to print the sorted Array of stringfunction printArraytString(str){ console.log(str.join(" "));}// Driver codearray1 = ["Bananas", "do","not", "grow", "in","Mississippi"];// function callarray1.sort(compare);// print resultant ArrayprintArraytString(array1)// This code is contributed by Aditya Sharma |
do in not Mississippi Bananas grow
Time Complexity: O(n * log n)
Auxiliary Space: O(n)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
