'''
keys: 
Solutions:
Similar: 
T:
S:
'''
from typing import List


class Solution1:
    # https://leetcode.com/problems/largest-number/discuss/53298/Python-different-solutions-(bubble-insertion-selection-merge-quick-sorts).
    # bubble sort
    def largestNumber1(self, nums: List[int]) -> str:
        for i in range(len(nums)):
            for j in range(0, len(nums)-i-1):
                if not self.compare(nums[j], nums[j+1]):
                    nums[j], nums[j+1] = nums[j+1], nums[j]
        return str(int("".join(map(str, nums))))
        
    def compare(self, n1, n2):
        return str(n1) + str(n2) > str(n2) + str(n1)
        

        
        
# constructor version
class LargerNumKey(str):
    def __lt__(x, y):
        return x+y > y+x
        
class Solution:
    def largestNumber(self, nums):
        largest_num = ''.join(sorted(map(str, nums), key=LargerNumKey))
        return '0' if largest_num[0] == '0' else largest_num