Remove Digit From Number to Maximize Result

Hello Friends, can you please assist me with my implemeation to this leetcode question done in swift? I passes about 45 test cases out of 121.

You are given a string number representing a positive integer and a character digit.Return the resulting string after removing exactly one occurrence of digit from number such that the value of the resulting string in decimal form is maximized. The test cases are generated such that digit occurs at least once in number.

Example 1:

Input: number = "123", digit = "3" Output: "12" Explanation: There is only one '3' in "123". After removing '3', the result is "12".

Example 2:

Input: number = "1231", digit = "1" Output: "231" Explanation: We can remove the first '1' to get "231" or remove the second '1' to get "123". Since 231 > 123, we return "231".

Example 3:

Input: number = "551", digit = "5" Output: "51" Explanation: We can remove either the first or second '5' from "551". Both result in the string "51".

Constraints:

  • 2 <= number.length <= 100
  • numberconsists of digits from '1'to '9'.
  • digitis a digit from '1'to '9'.
  • digitoccurs at least once in number.

Solution:

class Solution {
    func removeDigit(_ number: String, _ digit: Character) -> String {
        var number = number
        var digit = digit
        var result = ""
        var removed = false
        
        for char in number{
            if char == digit && !removed{
                removed = true
            }
            else{
                result.append(char)
            }
        }
        return result
    }
}

Failed Test Case:
Input:
"133235"
"3"
Output:
"13235"
Expected:
"13325"

Hi! It seems that you skipped

such that the value of the resulting string in decimal form is maximized .

You need to somehow check which removal maximizes the result

How I would do it, without thinking much about the problem: try all the possibilities, convert them to numbers, and select the highest one

If we care about asymptotic complexity, where the input may be arbitrarily long with any number of occurrences of the given digit, then we can do this with a linear time algorithm:

  1. Find the first occurrence of the given digit where the next digit after it has a larger value. (Note: if the given digit is the largest possible, ie. a 9 for decimal numbers, then this step can be skipped.)
  2. If such a digit was found, remove it and return. (Note: if the found digit is immediately preceded by additional copies of the given digit, then any of them could be removed with the same result.)
  3. Otherwise, remove the last occurrence of the given digit. (Note: same comment as in step 2.)

Not only does this avoid potentially quadratic work from re-parsing the whole number with each candidate digit removed, but it also allows inputs that would overflow the size of an integer.

Of course, if you want to use this approach yourself, then you’ll need to include comments explaining why it works. And I’m not going to write those for you.

3 Likes

Can you please share your implementation? this question is too exhausting for me to solve. Ive spent hours try to solve tis.

Here is a simple, easy to verify, naive algorithm.

Delete each occurrence of the digit and collate the results. Then sort them in ascending order. The last value in the sorted results will be the answer.

Code
import Foundation

let numbers = ["126", "626", "676", "111611666", "111671666"]
let victim = Character ("6")

for number in numbers {
    print (number, "...")
    var candidates = [String] ()
    for i in 0..<number.count {
        var s = number
        let deleted = s.removeIfExists (victim, at: i)
        
        if deleted {
            candidates.append (s)
        }
    }
    
    if candidates.count > 0 {
        candidates = candidates.sorted ()
        for s in candidates {
            print ("\t", s)
        }
        print ("--> answer:", candidates.last!)
    }
}

// String.removeIfExists
// [https://forums.swift.org/t/how-to-delete-a-character-at-an-integer-index-from-a-string/61104/4]
//
extension String {
    mutating func removeIfExists (_ character: Character, at offset: Int) -> Bool {
        if let i = index (startIndex, offsetBy: offset, limitedBy: endIndex),
            i < endIndex,
            self [i] == character {
            remove (at: i)
            return true
        }
        else {
            return false
        }
    }
}

Edit: This algorithm was already proposed by @cukr, but I have missed it.

The most efficient method that I can think of is go through the string from left to right and stop at each occurrence of the specified digit. If the digit to the right of the digit you stopped at is bigger than the digit, remove the digit you stopped at and you have the answer. This works because replacing the leftmost digit possible with a larger digit is guaranteed to be a bigger solution than changing anything in the less significant digits of the solution. If you get to the end of the string and the algorithm hasn't stopped, just remove the rightmost occurrence of the digit.

This solution is also a lot faster than the naive solution because it only requires 1 string operation and zero large integer string to integer conversions. The tests you're failing on may be tests where the input number is larger than a 64-bit integer, that's just a guess though.

If you're struggling to implement that I'm happy to help, but I'd rather not just give you a full implementation for the solution.

1 Like

This is what Nevin said already though. The Reddit thread has the implementation.

Oops sorry, I somehow didn't see that comment, my bad :man_facepalming: