Python – Reverse Sort a String

Sorting has always been quite a popular utility with lots of applications everywhere, which Python language has opted for. Python in its language offers a sort function to perform this task. But due to the fact that not all the containers in Python are mutable, such as string, the sort function doesn’t work as it inplace tries to sort and immutability stops this. Let’s discuss certain ways in which a string can be sorted in a reverse way.

Method #1: join() + sorted() + reverse key: The combination of the above functions can potentially solve this particular problem. This task is performed in 2 steps in which the first step we get the reverse sorted list of characters and then we join the result to get the resultant sorted string. 

The original string : geekforLazyroar
String after reverse sorting : srokkggfeeee

Time Complexity: O(n*logn)
Auxiliary Space: O(n), where n is the number of characters in string.

Method #2: Using sorted() + reduce() + lambda: This particular task can also be performed using the combination of 3 functions. Here we join the resultant reverse sorted list of characters using the lambda function joined by the reduce function. Works only for Python2. 

The original string : geekforLazyroar
String after reverse sorting : srokkggfeeee

Method #3: Using list() + sort() + join(): This problem can also be solve using the combination of above 3 methods. Here we convert the string to a list and sort this list with the sort function of the list in reverse order and after that join the result into a string.

The original string : geekforLazyroar
String after reverse sorting : srokkggfeeee

Time Complexity: O(nlogn)
Auxiliary space: O(n)

Method #4: Using map() function and lambda expression

Step-by-step algorithm:

1. Initialize the list with elements containing the substring to be replaced.
2. Print the original list.
3. Use the map() function with lambda expression to replace the substring in each element of the list.
4. Convert the map object to list and store it in a variable.
5. Print the modified list.

Original List :  ['4', 'kg', 'butter', 'for', '40', 'bucks']
Modified List :  ['1', 'kg', 'butter', 'for', '10', 'bucks']

Time complexity: The time complexity of the map() function is O(n), where n is the number of elements in the list. The time complexity of the replace() function is O(m), where m is the length of the string. Therefore, the overall time complexity of the code is O(n*m).
Auxiliary space: The space complexity of the code depends on the size of the list and the size of the substring to be replaced. The map() function returns a map object, which is converted to a list and stored in a variable. Therefore, the space complexity of the code is O(n), where n is the number of elements in the list.

Method #5: Using a loop:

Step-by-step approach:

• Initialize the list test_list with the given values.
• Print the original list using the print() function.
• Loop through each element of the list using a for loop and the range() function.
• Replace the substring ‘4’ with ‘1’ in each element of the list using the replace() method of string objects.
• Update the original list with the modified elements using indexing.
• Print the modified list using the print() function.

Original List :  ['4', 'kg', 'butter', 'for', '40', 'bucks']
Modified List :  ['1', 'kg', 'butter', 'for', '10', 'bucks']

Time complexity: O(n), where n is the length of the list, because we need to loop through each element of the list once.
Auxiliary space: O(1), because we are modifying the original list in place and not using any additional data structures.

Method #6: Using list comprehension

Use a list comprehension to iterate over the elements of the original list and replace the substring ‘4’ with ‘1’. The new list is created in one line without using a loop.

Modified List :  ['1', 'kg', 'butter', 'for', '10', 'bucks']

Time complexity: O(n), where n is the length of the list. 
Auxiliary space: O(n) as well, since a new list is created.