Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1946.html

1946. Largest Number After Mutating Substring

Level

Medium

Description

You are given a string num, which represents a large integer. You are also given a 0-indexed integer array change of length 10 that maps each digit 0-9 to another digit. More formally, digit d maps to digit change[d].

You may choose to mutate any substring of num. To mutate a substring, replace each digit num[i] with the digit it maps to in change (i.e. replace num[i] with change[num[i]]).

Return a string representing the largest possible integer after mutating (or choosing not to) any substring of num.

A substring is a contiguous sequence of characters within the string.

Example 1:

Input: num = “132”, change = [9,8,5,0,3,6,4,2,6,8]

Output: “832”

Explanation: Replace the substring “1”:

  • 1 maps to change[1] = 8.

Thus, “132” becomes “832”.

“832” is the largest number that can be created, so return it.

Example 2:

Input: num = “021”, change = [9,4,3,5,7,2,1,9,0,6]

Output: “934”

Explanation: Replace the substring “021”:

  • 0 maps to change[0] = 9.
  • 2 maps to change[2] = 3.
  • 1 maps to change[1] = 4.

Thus, “021” becomes “934”.

“934” is the largest number that can be created, so return it.

Example 3:

Input: num = “5”, change = [1,4,7,5,3,2,5,6,9,4]

Output: “5”

Explanation: “5” is already the largest number that can be created, so return it.

Constraints:

  • 1 <= num.length <= 10^5
  • num consists of only digits 0-9.
  • change.length == 10
  • 0 <= change[d] <= 9

Solution

Use a greedy approach. Find the leftmost digit in num such that mutating the digit will increase num, and find the rightmost digit in num such that mutating the digit will decrease num. If such a leftmost digit does not exist, return num without mutating. If such a rightmost digit does not exist, then mutate all digits from the determined leftmost digit to the end of num. Finally, return the mutated num.

  • class Solution {
    public String maximumNumber(String num, int[] change) {
        char[] array = num.toCharArray();
        int length = array.length;
        int start = -1, end = length;
        for (int i = 0; i < length; i++) {
            int digit = array[i] - '0';
            if (digit < change[digit]) {
                start = i;
                break;
            }
        }
        if (start < 0)
            return num;
        for (int i = start + 1; i < length; i++) {
            int digit = array[i] - '0';
            if (digit > change[digit]) {
                end = i;
                break;
            }
        }
        for (int i = start; i < end; i++) {
            int digit = array[i] - '0';
            char changed = (char) ('0' + change[digit]);
            array[i] = changed;
        }
        return new String(array);
    }
}

############

class Solution {
    public String maximumNumber(String num, int[] change) {
        char[] s = num.toCharArray();
        for (int i = 0; i < s.length; ++i) {
            if (change[s[i] - '0'] > s[i] - '0') {
                for (; i < s.length && s[i] - '0' <= change[s[i] - '0']; ++i) {
                    s[i] = (char) (change[s[i] - '0'] + '0');
                }
                break;
            }
        }
        return String.valueOf(s);
    }
}

  • // OJ: https://leetcode.com/problems/largest-number-after-mutating-substring/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    string maximumNumber(string num, vector<int>& A) {
        bool changed = false;
        for (char &c : num) {
            int before = c - '0', after = A[before];
            if (after < before) {
                if (changed) break;
                continue;
            } else if (after == before) {
                continue;
            }
            changed = true;
            c = '0' + after;
        }
        return num;
    }
};

  • class Solution:
    def maximumNumber(self, num: str, change: List[int]) -> str:
        s = list(num)
        for i, c in enumerate(s):
            if change[int(c)] > int(c):
                while i < len(s) and int(s[i]) <= change[int(s[i])]:
                    s[i] = str(change[int(s[i])])
                    i += 1
                break
        return ''.join(s)

############

# 1946. Largest Number After Mutating Substring
# https://leetcode.com/problems/largest-number-after-mutating-substring/

class Solution:
    def maximumNumber(self, nums: str, change: List[int]) -> str:
        nums = list(nums)
        done = False
        
        for i, num in enumerate(nums):
            pos = int(num)
            if change[pos] >= pos:
                nums[i] = str(change[pos])
                if change[pos] > pos:
                    done = True
            else:
                if done:
                    break
        
        return "".join(nums)


  • func maximumNumber(num string, change []int) string {
	s := []byte(num)
	for i, c := range num {
		if change[c-'0'] > int(c-'0') {
			for ; i < len(s) && change[s[i]-'0'] >= int(s[i]-'0'); i++ {
				s[i] = byte(change[s[i]-'0']) + '0'
			}
			break
		}
	}
	return string(s)
}

All Problems

All Solutions