algoadvance

You are given a non-negative integer num represented as a string. You can swap two digits at most once to get the maximum valued number. Return the maximum valued number you can get.

Example 1:

Input: num = "2736"
Output: "7236"
Explanation: Swap the number 2 and the number 7.

Example 2:

Input: num = "9973"
Output: "9973"
Explanation: No swap needed.

Constraints:

• 0 <= num <= 10^8

Clarifying Questions

1. Input type: Is the input always given as a string?
   • Yes, the input num is always a string.
2. Output type: Should the output also be a string?
   • Yes, the output should also be a string.
3. Number of swaps: Can we perform more than one swap?
   • No, we can perform at most one swap.
4. Leading zeros: Should we consider cases where the number might end up with leading zeros after swapping?
   • Since num is a non-negative integer represented as a string, and given the nature of the problem, leading zeros should not occur.

Strategy

1. Convert the string into a list of characters for easier manipulation.
2. Iterate through the string to identify the maximum number we can form by swapping any two digits.
3. Use a right-to-left traversal to keep track of the last seen positions of each digit.
4. For each digit from left to right, check if there is a larger digit available further in the list.
5. If found, swap and convert the list back to a string, then return it.

Code

def maximumSwap(num: str) -> str:
    # Convert the string to a list of characters to make manipulation easier
    num_list = list(num)
    n = len(num_list)
    
    # Create a dictionary to track the last index of each digit in the string
    last = {int(d): i for i, d in enumerate(num_list)}
    
    # Traverse the string from the beginning to find where to make the swap
    for i, d in enumerate(num_list):
        # Check for any larger digit after the current position
        for digit in range(9, int(d), -1):
            if last.get(digit, -1) > i:
                # Swap the current digit with the larger digit found
                num_list[i], num_list[last[digit]] = num_list[last[digit]], num_list[i]
                # Convert list back to string and return the result
                return ''.join(num_list)
    
    # If no swap has been made, return the original number
    return num

# Example usage
print(maximumSwap("2736"))  # Output: "7236"
print(maximumSwap("9973"))  # Output: "9973"

Time Complexity

• Constructing the last dictionary takes O(n) time where n is the length of the string.
• The nested loop to find the swap operates in O(n) time (since outer loop runs n times and inner loop is bounded by a constant, i.e., 10 digits).
• Overall time complexity is O(n) where n is the length of the string num.

Space Complexity

• The primary additional space used is for the last dictionary which holds up to 10 entries (one for each digit from 0 to 9), making the space complexity O(1).
• The list num_list takes O(n) space to store the characters of the input string.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?