Sometimes, while working with python strings, we can have a problem in which we desire to extract particular list which has most number of unique characters. This kind of problem can have application in competitive programming and web development domain. Lets discuss certain ways in which this task can be performed.
Method #1 : Using max() + dictionary comprehension The combination of above functionalities can be used to perform this task. In this, we firstly collect the frequency of each character using dictionary and then employ max() to compute the string with most unique characters.
Python3
# Python3 code to demonstrate # String with most unique characters# using max() + dictionary comprehension# Initializing listtest_list = ['gfg', 'is', 'best', 'for', 'Lazyroarc']# printing original listprint("The original list is : " + str(test_list))# String with most unique characters# using max() + dictionary comprehensiontemp = {idx : len(set(idx)) for idx in test_list}res = max(temp, key = temp.get)# printing result print ("The string with most unique characters is : " + str(res)) |
The original list is : ['gfg', 'is', 'best', 'for', 'Lazyroarc'] The string with most unique characters is : Lazyroarc
Time Complexity: O(n) where n is the number of elements in the list “test_list”.
Auxiliary Space: O(n) where n is the number of elements in the list “test_list”.
Method #2 : Using max() + key + lambda The combination of above methods can be used to perform this task. In this, we perform this task in similar way as above, just the difference is instead of using comprehension we use lambda function to extend logic to each string for computation.
Python3
# Python3 code to demonstrate # String with most unique characters# using max() + key + lambda# Initializing listtest_list = ['gfg', 'is', 'best', 'for', 'Lazyroarc']# printing original listprint("The original list is : " + str(test_list))# String with most unique characters# using max() + key + lambdares = max(test_list, key = lambda sub: len(set(sub)), default = None)# printing result print ("The string with most unique characters is : " + str(res)) |
The original list is : ['gfg', 'is', 'best', 'for', 'Lazyroarc'] The string with most unique characters is : Lazyroarc
Method#3:Using Counter()+keys()+list() functions
Python3
# Python3 code to demonstrate# String with most unique charactersfrom collections import Counter# Initializing listtest_list = ['gfg', 'is', 'best', 'for', 'Lazyroarc']# printing original listprint("The original list is : " + str(test_list))# String with most unique charactersres = []stringres = ""for i in test_list: freq = Counter(i) if(len(freq) >= len(res)): res = list(freq.keys()) stringres = i# printing resultprint("The string with most unique characters is : " + str(stringres)) |
The original list is : ['gfg', 'is', 'best', 'for', 'Lazyroarc'] The string with most unique characters is : Lazyroarc
Time Complexity: O(N)
Auxiliary Space: O(N)
Method #4 : Using numpy
Note: Install numpy module using command “pip install numpy”
Python3
# Python3 code to demonstrate# String with most unique characters# using max() + dictionary comprehension # Importing numpy libraryimport numpy as np# Initializing listtest_list = ['gfg', 'is', 'best', 'for', 'Lazyroarc'] # printing original listprint("The original list is : " + str(test_list)) # String with most unique characters# using max() + dictionary comprehensiontemp = {idx : len(np.unique(list(idx))) for idx in test_list}res = max(temp, key = temp.get) # printing resultprint ("The string with most unique characters is : " + str(res))#This code is contributed by Edula Vinay Kumar Reddy |
Output:
The original list is : [‘gfg’, ‘is’, ‘best’, ‘for’, ‘Lazyroarc’]
The string with most unique characters is : Lazyroarc
Explanation:
- In this code, we are importing the numpy library to use np.unique() function.
- We initialize a list test_list of strings.
- We use a dictionary comprehension to create a dictionary temp with the length of unique characters in each string of test_list as the values and the corresponding strings as keys.
- The np.unique() function takes a list as input and returns an array of unique elements of that list.
- Then, we use the max() function with temp.get as the key to get the string with the most number of unique characters.
- The result is the string with the most number of unique characters.
Time complexity: O(N)
Auxiliary space: O(N)
Method #5 : Using sorted() function and len() function
- Convert the list to tuples where each tuple contains: the string and its set of unique characters.
- Sort the list of tuples by the length of the set of unique characters in descending order.
- Return the first element of the sorted list of tuples, which will be the string with the most unique characters.
Python3
# Python3 code to demonstrate # String with most unique characters# Initializing listtest_list= ['gfg', 'is', 'best', 'for', 'Lazyroarc']# printing original listprint("The original list is : " + str(test_list))# creating list of tuples with string and its set of unique characterslist_tuples = [(s, set(s)) for s in test_list]# sorting the list of tuplessorted_list = sorted(list_tuples, key=lambda x: len(x[1]), reverse=True)# returning the first elementresult = sorted_list[0][0]# printing result print ("The string with most unique characters is : "+ str(result)) |
The original list is : ['gfg', 'is', 'best', 'for', 'Lazyroarc'] The string with most unique characters is : Lazyroarc
Time complexity: O(N*log(N)) as for sorting the list of strings, and then O(n) for iterating over the sorted list
Auxiliary space: O(N) as we are creating the sorted list of strings .
Method #6: Using for loop and dictionary
Algorithm:
- Initialize an empty string variable max_str and a variable max_count to 0.
- Iterate over each string s in the list test_list:
a. Initialize an empty dictionary char_dict to store the unique characters of s.
b. Iterate over each character c in s:
i. If c is not already in char_dict, add it with a value of 1.
c. Calculate the length of char_dict and store it in the variable count.
d. If count is greater than max_count, update max_count to count and max_str to s. - Print the value of max_str
Python3
test_list = ['gfg', 'is', 'best', 'for', 'Lazyroarc']# printing original listprint("The original list is : " + str(test_list))max_str = ''max_count = 0for s in test_list: char_dict = {} for c in s: if c not in char_dict: char_dict = 1 count = len(char_dict) if count > max_count: max_count = count max_str = sprint(f"The string with most unique characters is: {max_str}")#This code is contributed by Vinay Pinjala. |
The original list is : ['gfg', 'is', 'best', 'for', 'Lazyroarc'] The string with most unique characters is: Lazyroarc
The time complexity of this algorithm is O(n*m), where n is the length of the input list test_list and m is the maximum length of a string in test_list.
The outer loop iterates over each string in the list once, and the inner loop iterates over each character of the string once. Therefore, the time complexity is proportional to the number of strings times the maximum length of a string.
The auxiliary space of this algorithm is also O(n*m), because we create a dictionary for each string in the list, with a maximum size of m characters. Therefore, the space required is proportional to the number of strings times the maximum length of a string.
