Formatted question description: https://leetcode.ca/all/1881.html
1881. Maximum Value after Insertion
Level
Medium
Description
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** maximize n
’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
andx = 6
, it would be best to insert it between7
and3
, makingn = 763
. - If
n = -55
andx = 2
, it would be best to insert it before the first5
, makingn = -255
.
Return a string representing the maximum value of n
after the insertion.
Example 1:
Input: n = “99”, x = 9
Output: “999”
Explanation: The result is the same regardless of where you insert 9.
Example 2:
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
If n
is positive, find the leftmost digit in n
that is less than x
and insert x
to the left of the digit. If no such digit is found, insert x
at the end of n
.
If n
is negative, find the leftmost digit in n
that is greater than x
and insert x
to the left of the digit. If no such digit is found, insert x
and the end of n
.
class Solution {
public String maxValue(String n, int x) {
char xChar = (char) (x + '0');
if (n.charAt(0) != '-')
return maxValuePositive(n, xChar);
else
return maxValueNegative(n, xChar);
}
public String maxValuePositive(String n, char x) {
StringBuffer sb = new StringBuffer(n);
int length = n.length();
int insertIndex = length;
for (int i = 0; i < length; i++) {
if (n.charAt(i) < x) {
insertIndex = i;
break;
}
}
sb.insert(insertIndex, x);
return sb.toString();
}
public String maxValueNegative(String n, char x) {
StringBuffer sb = new StringBuffer(n);
int length = n.length();
int insertIndex = length;
for (int i = 1; i < length; i++) {
if (n.charAt(i) > x) {
insertIndex = i;
break;
}
}
sb.insert(insertIndex, x);
return sb.toString();
}
}