We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Largest Number After Mutating Substring

Number: 2077

Difficulty: Medium

Paid? No

Companies: Infosys

Problem Description

We are given a string representing a large integer and an integer array (of length 10) that maps each digit 0-9 to another digit. We can choose to mutate one contiguous substring of the given number by replacing each digit with its mapped digit. The goal is to return the largest possible integer (as a string) after performing the mutation on a single substring. If mutating any substring does not produce a larger number, we return the original number.

Key Insights

  • We are allowed to perform the mutation operation on exactly one contiguous substring.
  • The mutation is beneficial only when the mapped digit is strictly greater than the original digit, so we should begin mutating at the first such occurrence.
  • After starting the mutation, continue as long as the change does not make the digit smaller than its original value; stop as soon as it does.
  • A greedy approach works here by iterating through the number and applying the transformation at the best opportunity.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the number, since we scan through the string once. Space Complexity: O(n) for creating a mutable copy of the string (or using additional space for the result).

Solution

The solution involves a greedy approach:

  1. Traverse the number from left to right.
  2. Begin the mutation when a digit is found that, after mapping, is greater than the original digit.
  3. Continue mutating consecutive digits as long as the new digit is not smaller than the original.
  4. Once the mutation results in a lesser digit, stop the process. This method ensures that the highest possible number is obtained by transforming only the optimal contiguous substring.

Code Solutions

# Python solution
class Solution:
    def maximumNumber(self, num: str, change: List[int]) -> str:
        # Convert the string to a list for easier in-place modifications
        num_list = list(num)
        started = False  # Flag indicating whether mutation has started

        for i in range(len(num_list)):
            original_digit = int(num_list[i])
            mutated_digit = change[original_digit]
            # Start mutation when the mapped digit is strictly greater than the original
            if not started and mutated_digit > original_digit:
                num_list[i] = str(mutated_digit)
                started = True
            # Continue mutation as long as the mapped digit is at least the original
            elif started:
                if mutated_digit >= original_digit:
                    num_list[i] = str(mutated_digit)
                else:
                    break  # Stop mutating if the mapped digit is less than the original

        return "".join(num_list)
← Back to All Questions