Largest number order in string

Question

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"

Answer 1

This is an improvement on the answer by @coderodde. Just like they said, you can do this in \$\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 \$\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.

Answer 2

Cannot comment on Python, but what comes to to the actual algorithm, you can do it in linear time \$\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.

Answer 3

• 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(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))