Problem

You are given a very large integer n, represented as a string,​​​​​​ and an integer digit x. The digits in n and the digit x are in the inclusive range [1, 9], and n may represent a negative number.

You want to maximizen’ s numerical value by inserting x anywhere in the decimal representation of n​​​​​​. You cannot insert x to the left of the negative sign.

  • For example, if n = 73 and x = 6, it would be best to insert it between 7 and 3, making n = 763.
  • If n = -55 and x = 2, it would be best to insert it before the first 5, making n = -255.

Return _a string representing themaximum value of _n ​​​​​​ after the insertion.

Examples

Example 1

1
2
3

Input: n = "99", x = 9
Output: "999"
Explanation: The result is the same regardless of where you insert 9.

Example 2

1
2
3

Input: n = "-13", x = 2
Output: "-123"
Explanation: You can make n one of {-213, -123, -132}, and the largest of those three is -123.

Constraints

  • 1 <= n.length <= 10^5
  • 1 <= x <= 9
  • The digits in n​​​ are in the range [1, 9].
  • n is a valid representation of an integer.
  • In the case of a negative n,​​​​​​ it will begin with '-'.

Solution

Method 1 – Greedy String Insertion

Intuition

To maximize the value, insert x at the earliest position where it increases the value. For positive numbers, insert before the first digit less than x. For negative numbers, insert before the first digit greater than x.

Approach

  1. If n is negative, start after the negative sign.
  2. For positive n, find the first digit less than x and insert x there.
  3. For negative n, find the first digit greater than x and insert x there.
  4. If no such position is found, append x at the end.
  5. Return the new string.

Complexity

  • ⏰ Time complexity: O(len(n)) — Scan the string once.
  • 🧺 Space complexity: O(len(n)) — For the result string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    string maxValue(string n, int x) {
        int i = 0;
        if (n[0] == '-') {
            i = 1;
            while (i < n.size() && n[i] <= '0' + x) ++i;
        } else {
            while (i < n.size() && n[i] >= '0' + x) ++i;
        }
        return n.substr(0, i) + to_string(x) + n.substr(i);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func maxValue(n string, x int) string {
    b := []byte(n)
    i := 0
    if b[0] == '-' {
        i = 1
        for i < len(b) && b[i] <= byte('0'+x) { i++ }
    } else {
        for i < len(b) && b[i] >= byte('0'+x) { i++ }
    }
    return n[:i] + string('0'+x) + n[i:]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public String maxValue(String n, int x) {
        int i = 0;
        if (n.charAt(0) == '-') {
            i = 1;
            while (i < n.length() && n.charAt(i) <= (char)('0'+x)) i++;
        } else {
            while (i < n.length() && n.charAt(i) >= (char)('0'+x)) i++;
        }
        return n.substring(0, i) + x + n.substring(i);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun maxValue(n: String, x: Int): String {
        var i = 0
        if (n[0] == '-') {
            i = 1
            while (i < n.length && n[i] <= ('0'+x)) i++
        } else {
            while (i < n.length && n[i] >= ('0'+x)) i++
        }
        return n.substring(0, i) + x + n.substring(i)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def max_value(n: str, x: int) -> str:
    i = 0
    if n[0] == '-':
        i = 1
        while i < len(n) and int(n[i]) <= x:
            i += 1
    else:
        while i < len(n) and int(n[i]) >= x:
            i += 1
    return n[:i] + str(x) + n[i:]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn max_value(n: String, x: i32) -> String {
        let b = n.as_bytes();
        let mut i = 0;
        if b[0] == b'-' {
            i = 1;
            while i < b.len() && b[i] <= b'0' + x as u8 { i += 1; }
        } else {
            while i < b.len() && b[i] >= b'0' + x as u8 { i += 1; }
        }
        let mut res = n[..i].to_string();
        res.push_str(&x.to_string());
        res.push_str(&n[i..]);
        res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    maxValue(n: string, x: number): string {
        let i = 0;
        if (n[0] === '-') {
            i = 1;
            while (i < n.length && +n[i] <= x) i++;
        } else {
            while (i < n.length && +n[i] >= x) i++;
        }
        return n.slice(0, i) + x + n.slice(i);
    }
}