Given a list of strings Str, find the largest string among all. The largest string is the string with the largest number of unique characters.
Example:
Input: Str[] = {“AN KOW”, “LO JO”, “ZEW DO RO” }
Output: “ZEW DO RO”
Explanation: “ZEW DO RO” has maximum distinct letters.Input: Str[] = {“ROMEO”, “EMINEM”, “RADO”}
Output: “ROMEO”
Explanation: In case of tie, we can print any of the strings.
Approach: We iterate over the strings and take a boolean array to check the presence of letters. Also, keep track of the maximum unique letters. Return the string with the maximum number of distinct characters.
Below is the implementation of the above approach:
C++
// C++ code to find // the largest string #include <bits/stdc++.h> using namespace std; // Function to find string // with maximum number of // unique characters. void LargestString(string* na, int N) { // To keep track of maximum unique character // string int maxx = 0; string result; // iterate through // all strings for ( int j = 0; j < N; j++) { // array indicating any // alphabet included or // not included bool character[26]; // To count the unique character int count = 0; // count number of unique // alphabets in each string for ( int k = 0; k < na[j].size(); k++) { int x = ( int )(na[j][k] - 'A' ); if (na[j][k] != ' ' && character[x] == false ) { count++; character[x] = true ; } } // keep track of maximum // number of alphabets if (count > maxx){ result = na[j]; maxx = count; } } // print result cout << result << endl; } // Driver code int main() { string na[] = { "BOB" , "A AB C JOHNSON" , "ANJALI" , "ASKRIT" , "ARMAN MALLIK" }; int N = sizeof (na) / sizeof (na[0]); LargestString(na, N); } // This code is contributed by // Manish Shaw(manishshaw1) |
Java
// Java code to find the largest string import java.io.*; import java.lang.*; import java.util.Arrays; class Geek { // Function to find string with maximum // number of unique characters. public static void LargestString(String na[]) { int N = na.length; int c[] = new int [N]; // To keep track of maximum unique character // string int maxx = 0 ; String result = "" ; // iterate through all strings for ( int j = 0 ; j < N; j++) { // array indicating any alphabet // included or not included boolean character[] = new boolean [ 26 ]; // To count the unique character int count = 0 ; // count number of unique alphabets in each // string for ( int k = 0 ; k < na[j].length(); k++) { int x = na[j].charAt(k) - 'A' ; if ((na[j].charAt(k) != ' ' ) && (character[x] == false )) { count++; character[x] = true ; } } // keep track of maximum number of alphabets if (count > maxx) { result = na[j]; maxx = count; } } // print result System.out.println(result); } // Driver code public static void main(String[] args) { String na[] = { "BOB" , "A AB C JOHNSON" , "ANJALI" , "ASKRIT" , "ARMAN MALLIK" }; LargestString(na); } } |
Python3
# Python3 code to find the largest string # Function to find string with maximum # number of unique characters. def LargestString(na): N = len (na) c = [ 0 ] * N # To keep track of maximum unique character # string maxx = 0 result = "" # Iterate through all strings for j in range (N): # Array indicating any alphabet # included or not included character = [ False ] * 26 # To count the unique character count = 0 # count number of unique # alphabets in each string for k in range ( len (na[j])): x = ord (na[j][k]) - ord ( 'A' ) if ((na[j][k] ! = ' ' ) and (character[x] = = False )): count + = 1 character[x] = True # keep track of maximum # number of alphabets if (count > maxx): result = na[j] maxx = count # print result print (result) # Driver code na = [ "BOB" , "A AB C JOHNSON" , "ANJALI" , "ASKRIT" , "ARMAN MALLIK" ] LargestString(na) # This article is Contributed by Sharad Bhardwaj. |
C#
// Include namespace system using System; public class Geek { // Function to find string with maximum // number of unique characters. public static void LargestString(String[] na) { var N = na.Length; int [] c = new int [N]; // To keep track of maximum unique character // string var maxx = 0; var result = "" ; // iterate through all strings for ( int j = 0; j < N; j++) { // array indicating any alphabet // included or not included bool [] character = new bool [26]; // To count the unique character var count = 0; // count number of unique alphabets in each // string for ( int k = 0; k < na[j].Length; k++) { var x = ( int )(na[j][k]) - ( int )( 'A' ); if ((na[j][k] != ' ' ) && (character[x] == false )) { count++; character[x] = true ; } } // keep track of maximum number of alphabets if (count > maxx) { result = na[j]; maxx = count; } } // print result Console.WriteLine(result); } // Driver code public static void Main(String[] args) { String[] na = { "BOB" , "A AB C JOHNSON" , "ANJALI" , "ASKRIT" , "ARMAN MALLIK" }; Geek.LargestString(na); } } // This code is contributed by aadityaburujwale. |
Javascript
// JavaScript code to find // the largest string // Function to find string // with maximum number of // unique characters. function LargestString(na, N) { // To keep track of maximum unique character // string let maxx = 0; let result; // iterate through // all strings for (let j = 0; j < N; j++) { // array indicating any // alphabet included or // not included let character = new Array(26).fill( false ); // To count the unique character let count = 0; // count number of unique // alphabets in each string for (let k = 0; k < na[j].length; k++) { let x = na[j][k].charCodeAt() - 'A' .charCodeAt(); if (na[j][k] != ' ' && character[x] == false ) { count++; character[x] = true ; } } // keep track of maximum // number of alphabets if (count > maxx) { result = na[j]; maxx = count; } } // print result console.log(result); } // Driver code let na = [ "BOB" , "A AB C JOHNSON" , "ANJALI" , "ASKRIT" , "ARMAN MALLIK" ]; let N = na.length; LargestString(na, N); // This code is contributed by akashish__ |
BOB
Time Complexity: O(n*m), where n is the size of the given string array and m is the largest size of the string present in the given array.
Auxiliary Space: O(1)
Approach #2: Using Set Data Structure
We iterate over the array of strings and define a set of characters for every word in the array to check the number of unique characters of a word. Also, keep track of the maximum number of unique letters of that word. Return the string with the maximum number of distinct characters.
Below is the implementation of the above approach:
C++
// C++ code to find the largest string // with maximum number of unique characters #include <bits/stdc++.h> using namespace std; // Function to find string with // maximum number of unique characters. string largestString(vector<string> s, int n) { // To keep track of maximum // unique character string int maxi = 0; string result; // iterate through all string for ( auto it : s) { string word = it; // define a set of character // set will store all the unique // characters of a word unordered_set< char > st; // Iterate through the word and insert // every character of the word except ' '. for ( int i = 0; i < word.size(); i++) { if (word[i] != ' ' ) { st.insert(word[i]); } } // keep track of maximum number of alphabets // st.size() will be the number of // unique characters of a word if (st.size() > maxi) { maxi = st.size(); result = word; } } return result; } // Driver Code int main() { vector<string> s = { "BOB" , "A AB C JOHNSON" , "ANJALI" , "ASKRIT" , "ARMAN MALLIK" }; int n = s.size(); // Function call cout << largestString(s, n); return 0; } |
Java
// Java code to find the largest string // with maximum number of unique characters import java.util.*; class GFG { // Function to find string with // maximum number of unique characters. public static String largestString(String[] s, int n) { // To keep track of maximum // unique character string int maxi = 0 ; String result = "" ; // iterate through all string for (String word : s) { // define a set of character // set will store all the unique // characters of a word Set<Character> st = new HashSet<>(); // Iterate through the word and insert // every character of the word except ' '. for ( int i = 0 ; i < word.length(); i++) { if (word.charAt(i) != ' ' ) { st.add(word.charAt(i)); } } // keep track of maximum number of alphabets // st.size() will be the number of // unique characters of a word if (st.size() > maxi) { maxi = st.size(); result = word; } } return result; } // Driver code public static void main(String[] args) { String[] s = new String[] { "BOB" , "A AB C JOHNSON" , "ANJALI" , "ASKRIT" , "ARMAN MALLIK" }; int n = s.length; // Function call System.out.println(largestString(s, n)); } } // This Code is Contributed by Prasad Kandekar(prasad264) |
Python3
# Python code to find the largest string # with maximum number of unique characters from typing import List # Function to find string with # maximum number of unique characters. def largestString(s, n): # To keep track of maximum # unique character string maxi = 0 result = "" # iterate through all string for word in s: # define a set of character # set will store all the unique # characters of a word st = set () # Iterate through the word and insert # every character of the word except ' '. for char in word: if char ! = ' ' : st.add(char) # keep track of maximum number of alphabets # len(st) will be the number of # unique characters of a word if len (st) > maxi: maxi = len (st) result = word return result # Driver Code s = [ "BOB" , "A AB C JOHNSON" , "ANJALI" , "ASKRIT" , "ARMAN MALLIK" ] n = len (s) # Function call print (largestString(s, n)) # This Code is Contributed by Prasad Kandekar(prasad264) |
C#
// C# code to find the largest string // with maximum number of unique characters using System; using System.Collections.Generic; public class GFG { // Function to find string with maximum // number of unique characters. public static string LargestString(List< string > s, int n) { // To keep track of maximum unique // character string int maxi = 0; string result = "" ; // iterate through all string foreach ( string it in s) { string word = it; // define a set of character // set will store all the unique // characters of a word HashSet< char > st = new HashSet< char >(); // Iterate through the word and insert // every character of the word except ' '. for ( int i = 0; i < word.Length; i++) { if (word[i] != ' ' ) { st.Add(word[i]); } } // keep track of maximum number of alphabets // st.Count will be the number of // unique characters of a word if (st.Count > maxi) { maxi = st.Count; result = word; } } return result; } // Driver Code public static void Main() { List< string > s = new List< string >{ "BOB" , "A AB C JOHNSON" , "ANJALI" , "ASKRIT" , "ARMAN MALLIK" }; int n = s.Count; // Function call Console.WriteLine(LargestString(s, n)); } } // This Code is Contributed by Prasad Kandekar(prasad264) |
Javascript
// JS code to find the largest string // with maximum number of unique characters // Function to find string with // maximum number of unique characters. function largestString( s, n) { // To keep track of maximum // unique character string let maxi = 0; let result= "" ; // iterate through all string for (let it of s) { let word = it; // define a set of character // set will store all the unique // characters of a word let st = new Set(); // Iterate through the word and insert // every character of the word except ' '. for (let i = 0; i < word.length; i++) { if (word[i] != ' ' ) { st.add(word[i]); } } // keep track of maximum number of alphabets // st.size() will be the number of // unique characters of a word if (st.size > maxi) { maxi = st.size; result = word; } } return result; } // Driver Code let s = [ "BOB" , "A AB C JOHNSON" , "ANJALI" , "ASKRIT" , "ARMAN MALLIK" ]; let n = s.length; // Function call console.log(largestString(s, n)); // This code is contributed by ratiagrawal. |
A AB C JOHNSON
Complexity Analysis:
- Time Complexity: O(n * m), where n is the number of strings in the input vector and m is the average length of the strings.
- Auxiliary Space: O(m) as the maximum size of the set used to store unique characters would be the length of the longest string.
Approach (Using Priority_queue):
- Initialize a priority queue pq to keep track of the strings with the highest number of unique characters.
- Iterate over each string in the input list strList.
- For each string, initialize a map count to keep track of the count of each character in the string, and a variable uniqueCount to keep track of the number of unique characters in the string.
- Iterate over each character in the string. If the character is not a space, increment the count of the corresponding key in the count map. If the count of the character is 1, increment uniqueCount.
- Push the current string and its uniqueCount value into the priority queue pq.
- After iterating over all the strings in strList, return the second element (i.e., the string) of the top element in pq.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; string largestString(vector<string> strList) { priority_queue<pair< int , string>> pq; for (string str : strList) { map< char , int > count; int uniqueCount = 0; for ( char c : str) { if (c != ' ' ) { count++; if (count == 1) { uniqueCount++; } } } pq.push({uniqueCount, str}); } return pq.top().second; } int main() { vector<string> strList = { "AN KOW" , "LO JO" , "ZEW DO RO" }; cout << largestString(strList) << endl; return 0; } |
Java
import java.util.*; class Main { static String largestString(List<String> strList) { PriorityQueue<Map.Entry<Integer, String>> pq = new PriorityQueue<>( (a, b) -> Integer.compare(b.getKey(), a.getKey()) ); for (String str : strList) { Map<Character, Integer> count = new HashMap<>(); int uniqueCount = 0 ; for ( char c : str.toCharArray()) { if (c != ' ' ) { count.put(c, count.getOrDefault(c, 0 ) + 1 ); if (count.get(c) == 1 ) { uniqueCount++; } } } pq.offer( new AbstractMap.SimpleEntry<>(uniqueCount, str)); } return pq.poll().getValue(); } public static void main(String[] args) { List<String> strList = Arrays.asList( "AN KOW" , "LO JO" , "ZEW DO RO" ); System.out.println(largestString(strList)); } } |
Python3
import heapq from collections import defaultdict def largestString(strList): # Initialize a max heap to store pairs of (uniqueCount, str) pq = [] for string in strList: count = defaultdict( int ) uniqueCount = 0 # Count the frequency of each character in the string and # calculate the number of unique characters (excluding spaces) for char in string: if char ! = ' ' : count[char] + = 1 if count[char] = = 1 : uniqueCount + = 1 # Push the pair (uniqueCount, str) into the max heap # using negation of uniqueCount to simulate max heap behavior heapq.heappush(pq, ( - uniqueCount, string)) # The top of the max heap contains the pair with the maximum uniqueCount # Pop the top pair and return the corresponding string return heapq.heappop(pq)[ 1 ] if __name__ = = "__main__" : strList = [ "AN KOW" , "LO JO" , "ZEW DO RO" ] print (largestString(strList)) # This code is contributed by shivamgupta0987654321 |
C#
// C# code implementation using System; using System.Collections.Generic; // creating Priority Queue class PriorityQueue<T> { private List<T> heap = new List<T>(); private Comparison<T> comparator; public PriorityQueue(Comparison<T> comparator) { this .comparator = comparator; } // Push method public void Push(T value) { heap.Add(value); heap.Sort(comparator); } // Pop method public T Pop() { T value = heap[0]; heap.RemoveAt(0); return value; } public bool IsEmpty() { return heap.Count == 0; } } class Program { // function called static string LargestString(List< string > strList) { // inserting in the queue PriorityQueue<Tuple< int , string >> pq = new PriorityQueue<Tuple< int , string >>( (a, b) => b.Item1 - a.Item1 ); foreach ( string str in strList) { // creating dictionary Dictionary< char , int > count = new Dictionary< char , int >(); int uniqueCount = 0; foreach ( char c in str) { if (c != ' ' ) { if (!count.ContainsKey(c)) count = 0; count++; if (count == 1) { uniqueCount++; } } } // pushing unique count pq.Push( new Tuple< int , string >(uniqueCount, str)); } return pq.Pop().Item2; } // Driver code static void Main( string [] args) { // input string List< string > strList = new List< string > { "AN KOW" , "LO JO" , "ZEW DO RO" }; // output Console.WriteLine(LargestString(strList)); } } |
Javascript
class PriorityQueue { constructor(comparator) { this .heap = []; this .comparator = comparator; } push(value) { this .heap.push(value); this .heap.sort( this .comparator); } pop() { return this .heap.shift(); } isEmpty() { return this .heap.length === 0; } } function largestString(strList) { const pq = new PriorityQueue((a, b) => b[0] - a[0]); for (const str of strList) { const count = new Map(); let uniqueCount = 0; for (const c of str) { if (c !== ' ' ) { count.set(c, (count.get(c) || 0) + 1); if (count.get(c) === 1) { uniqueCount++; } } } pq.push([uniqueCount, str]); } return pq.pop()[1]; } const strList = [ "AN KOW" , "LO JO" , "ZEW DO RO" ]; // Print the result console.log(largestString(strList)); |
ZEW DO RO
Time Complexity: O(n * m * log k), where n is the number of strings in strList, m is the maximum length of a string in strList, and k is the size of the priority queue.
Space Complexity: O(n * m), where n is the number of strings in strList and m is the maximum length of a string in strList.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!