Skip to content

1946. Largest Number After Mutating Substring 👎

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  string maximumNumber(string num, vector<int>& change) {
    bool mutated = false;

    for (char& c : num) {
      const int d = c - '0';
      c = '0' + max(d, change[d]);
      if (mutated && d > change[d])
        return num;
      if (d < change[d])
        mutated = true;
    }

    return num;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public String maximumNumber(String num, int[] change) {
    StringBuilder sb = new StringBuilder(num);
    boolean mutated = false;

    for (int i = 0; i < num.length(); ++i) {
      final int d = num.charAt(i) - '0';
      final char c = (char) ('0' + Math.max(d, change[d]));
      sb.setCharAt(i, c);
      if (mutated && d > change[d])
        return sb.toString();
      if (d < change[d])
        mutated = true;
    }

    return sb.toString();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def maximumNumber(self, num: str, change: List[int]) -> str:
    numList = list(num)
    mutated = False

    for i, c in enumerate(numList):
      d = int(c)
      numList[i] = chr(ord('0') + max(d, change[d]))
      if mutated and d > change[d]:
        return ''.join(numList)
      if d < change[d]:
        mutated = True

    return ''.join(numList)