"""Given a string n, a multi-digit number, write a function rearranging_digits to return a string of the smallest number
 larger than n that can be created by rearranging the digits in n. Return None if no such number exists.
"""


# we can generate all possible numbers from the digits in n,
# then we can get all bigger ones than n and choose the smallest.
# This solution will work, but generating all these permutations is very time and space-intensive
# (time and space complexity of O(n!)O(n!)).
# Better way
# Another example n = 356421 the answer will be 365421, generated by four steps.
# divide the first part 35 from sorted descending part 6421.
# get the least number of the first part, 6, replace it with the biggest number from the sorted part 5421 which is 5
# then we would have the two parts 36 and 5421.
# sort the second part ascending to be 1245.
# append the two parts together to have finally the result 361245.

def rearranging_digits(n):

    def smallest_bigger(target_digit, remaining_digits):
        # initially set largest number in remaining_digits
        next_digit = max(remaining_digits)
        # find the smallest num bigger than target_digit
        for num in remaining_digits:
            if target_digit < num < next_digit:
                next_digit = num
        return next_digit

    # Holds all digits
    total_digits = [int(str_digit) for str_digit in n]
    # the first portion, starts empty
    have_digits = []
    # The remaining portion, stated with all digits
    remaining_digits = total_digits.copy()
    for _ in range(len(total_digits)):
        # Generate the Descending sorted from the remaining digits
        desc_digits = sorted(remaining_digits, reverse=True)
        # if the remaining digits is sorted in Descending order
        if remaining_digits == desc_digits:
            if len(have_digits) == 0:
                return None
            else:
                # we swap the least digit with the smallest digit larger than that digit.
                have_digits[-1], moved_digit = smallest_bigger(have_digits[-1],
                                                           remaining_digits), have_digits[-1]
                remaining_digits.remove(have_digits[-1])
                remaining_digits.append(moved_digit)
                return ''.join(map(str, have_digits)) + ''.join(map(str, sorted(remaining_digits)))

        have_digits.append(remaining_digits[0])
        del remaining_digits[0]


n = '356421'
print(rearranging_digits(n))
