Sometimes, we can also encounter a problem in which we are given a mixed list and require to find the lexicographically smallest string that occur in list. This problem can find it’s application day-day programming. Let’s discuss certain ways in which this problem can be solved.
Method #1 : Using min() + isinstance() + list comprehension This task can be performed using the combination of above functions. In this, the min() functions performs the task of finding smallest string and isinstance() is used to check for string.
Python3
# Python3 code to demonstrate working of# Lexicographically smallest string in mixed list# Using min() + isinstance() + list comprehension# initializing listtest_list = [1, 2, 4, "GFG", 5, "IS", 7, "BEST"]# printing original listprint("The original list is : " + str(test_list))# Lexicographically smallest string in mixed list# Using min() + isinstance() + list comprehensionres = min(sub for sub in test_list if isinstance(sub, str))# printing result print("The Lexicographically smallest string is : " + str(res)) |
The original list is : [1, 2, 4, 'GFG', 5, 'IS', 7, 'BEST'] The Lexicographically smallest string is : BEST
Time Complexity: O(n*n) where n is the number of elements in the list “test_list”.
Auxiliary Space: O(1), constant extra space is required
Method #2 : Using min() + lambda + filter() The combination of above functions can also be used to perform this particular task. In this we perform the task of list comprehension using filter() and lambda and min function is used to performed the usual task of finding smallest string.
Python3
# Python3 code to demonstrate working of# Lexicographically smallest string in mixed list# Using min() + lambda + filter()# initializing listtest_list = [1, 2, 4, "GFG", 5, "IS", 7, "BEST"]# printing original listprint("The original list is : " + str(test_list))# Lexicographically smallest string in mixed list# Using min() + lambda + filter()res = min(filter(lambda s:isinstance(s, str), test_list))# printing result print("The Lexicographically smallest string is : " + str(res)) |
The original list is : [1, 2, 4, 'GFG', 5, 'IS', 7, 'BEST'] The Lexicographically smallest string is : BEST
Time Complexity: O(n*n) where n is the number of elements in the list “res_list”.
Auxiliary Space: O(n), where n is the number of elements in the new res list
Method#3: Using Recursive method.
Algorithm:
- Define a recursive function that takes a list as input.
- If the list is empty, return a high-value string (e.g., ‘zzz’).
- If the first element of the list is a string, recursively call the function on the rest of the list and return the minimum of the first element and the result of the recursive call.
- If the first element of the list is not a string, recursively call the function on the rest of the list.
- Call the recursive function on the input list and return the result.
Python3
# Python3 code to demonstrate working of# Lexicographically smallest string in mixed list# Using Recursive methoddef recursive_min_string(test_list): if not test_list: return 'zzz' elif isinstance(test_list[0], str): return min(test_list[0], recursive_min_string(test_list[1:])) else: return recursive_min_string(test_list[1:])# initializing listtest_list = [1, 2, 4, "GFG", 5, "IS", 7, "BEST"]# printing original listprint("The original list is : " + str(test_list))# Lexicographically smallest string in mixed listres = recursive_min_string(test_list)# printing resultprint("The Lexicographically smallest string is : " + str(res)) |
The original list is : [1, 2, 4, 'GFG', 5, 'IS', 7, 'BEST'] The Lexicographically smallest string is : BEST
Time Complexity: O(n), where n is the length of the input list. The recursive function iterates over the entire list once, so the time complexity is linear in the length of the list.
Auxiliary Space: O(n), where n is the length of the input list. The recursive function creates a new stack frame for each element of the list, so the space complexity is linear in the length of the list.
Method#4: Using heapq:
Algorithm:
- Initialize the input list, test_list.
- Initialize an empty list, strings, to store all the string elements of the input list.
- Use list comprehension to get all the string elements from the input list.
- Use the heapq.nsmallest() method to get the lexicographically smallest string from the strings list.
- Print the lexicographically smallest string.
Python3
import heapq# initializing listtest_list = [1, 2, 4, "GFG", 5, "IS", 7, "BEST"]# printing original listprint("The original list is : " + str(test_list))# Lexicographically smallest string in mixed list# Using heapqstrings = [sub for sub in test_list if isinstance(sub, str)]res = heapq.nsmallest(1, strings)[0]# printing resultprint("The Lexicographically smallest string is : " + str(res))#This code is contributed by Jyothi pinjala. |
The original list is : [1, 2, 4, 'GFG', 5, 'IS', 7, 'BEST'] The Lexicographically smallest string is : BEST
Time Complexity:
Creating a list of all string elements using list comprehension takes O(n) time, where n is the length of the input list.
The heapq.nsmallest() method takes O(k log n) time, where k is the number of smallest elements to be retrieved and n is the length of the input list.
Here, k is 1, so the time complexity reduces to O(log n).
Thus, the overall time complexity of the code is O(n + log n), which can be simplified to O(n).
Space Complexity:
An empty list, strings, is created to store the string elements. This takes O(1) space.
The heapq.nsmallest() method creates a heap with the string elements, which takes O(k) space.
Here, k is 1, so the space complexity is O(1).
Thus, the overall space complexity of the code is O(1).
