Problem

Given a string, assuming the string is numbers only, rearrange the string to that it is the greatest possible number.

Below is my solution to the problem above. I’d like feedback mainly on the algorithm, as I wrote this up very quickly. I used comprehension syntax to find the largest num, which I’m trying to use more. Any other feedback is appreciated as well.

```
def largest_number(string: str) -> str:
"""
Given a string, organize the numbers such as the
rearrangement is now the largest possible number
"""
string = list(string)
largest = ""
for _ in string:
largest_num = str(max([int(num) for num in string]))
largest += largest_num
string[string.index(largest_num)] = -1
return largest
if __name__ == '__main__':
# Test Cases #
assert largest_number("12345") == "54321"
assert largest_number("4689123") == "9864321"
assert largest_number("9") == "9"
assert largest_number("1923") == "9321"
```

Solution

This is an improvement on the answer by @coderodde. Just like they said, you can do this in O(n)$\mathcal{O}(n)$ time by counting how often each digit appears and then using a fixed output format. However, I would use `collections.Counter`

from the standard library and string multiplication to achieve this goal:

```
from collections import Counter
def largest_number(string: str) -> str:
counters = Counter(map(int, string))
return "".join(str(d) * counters[d] for d in range(9, -1, -1))
```

Compared to sorting, as presented in the answer by @bullseye, and the original answer, this compares OK. It has a slight overhead for small strings due to the `Counter`

object, but in the end it is faster than hardcoding character values and on the same level as sorting, but not better.

However, all three are vastly better than your O(n2)$\mathcal{O}({n}^{2})$ algorithm (note the vastly different x limits):

As soon as you have three or more testcases, it might make sense to not repeat the testing code. Just put the input and expected output into a data structure (a list of tuples would do here), and iterate over it:

```
if __name__ == '__main__':
test_cases = [("12345", "54321"), ("4689123", "9864321"), ("9", "9"), ("", "")]
for string, expected in test_cases:
output = largest_number(string)
if output != expected:
raise AssertionError(f"{string!r} gave back {output!r}"
f" instead of {expected!r}")
```

For more complicated programs you might want to look at a testing framework like `unittest`

.

Cannot comment on Python, but what comes to to the actual algorithm, you can do it in linear time Θ(n)$\mathrm{\Theta}(n)$:

```
def largest_number_3(string: str) -> str:
counters = [0 for _ in range(10)]
string = list(string)
for ch in string:
counters[ord(ch) - ord('0')] += 1
i = 0
for num in range(9, -1, -1):
for _ in range(counters[num]):
string[i] = chr(num + ord('0'))
i += 1
return ''.join(string)
```

The above is just a counting sort since there is only 10 digits to distinguish.

**Confusing names:**the function`largest_number()`

has a`string`

parameter it’s generally not a good practice to name parameters by their types and their is a type hint in your code indicating what that is so you can call the parameter`digits`

.

Inside`largest_num()`

there is`string = list(string)`

where string is not a string(a list). This is super confusing when I’m looking at this part`string[string.index(largest_num)] = -1`

which I mistook for some line that should produce an error (because you can’t assign values to string indexes) and then I realized that string is a list. Don’t use such confusing names.**Adding to strings:**`largest += largest_num`

This form is inefficient, a string is immutable in Python and each time you’re adding to`largest`

a new string is created and assigned to the new value. Whenever you find a similar situation, use list comprehension and join it using the`str.join()`

method.-
**A better approach:**

As ‘coderodde’ indicated in the comments, this is an O(N2)$O({N}^{2})$ solution which can be simplified into the following by just sorting the string:`def maximize_number(digits: str) -> str: """Return the maximum number that can be formed using the digits.""" return ''.join(sorted(digits, reverse=True))`