Remove Digit From Number to Maximize Result

🏠 ⬅️ ➡️

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
  • number consists of digits from '1' to '9'.
  • digit is a digit from '1' to '9'.
  • digit occurs at least once in number.
Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
✅ Correct 
program main
    implicit none

    character(len=100) :: number
    character(len=100) :: digit
    character(len=100) :: result

    ! Examples
    number = "123"
    digit = "3"
    call solve(number, digit, result)
    write (*,*) trim(result)

    number = "1231"
    digit = "1"
    call solve(number, digit, result)
    write (*,*) trim(result)

    number = "551"
    digit = "5"
    call solve(number, digit, result)
    write (*,*) trim(result)

contains

    subroutine solve(number, digit, result)
        implicit none
        character(len=*), intent(in) :: number
        character(len=*), intent(in) :: digit
        character(len=*), intent(out) :: result

        integer :: i
        integer :: j
        integer :: n
        integer :: d

        n = len_trim(number)
        d = len_trim(digit)

        do i = 1, n - d + 1
            if (number(i:i+d-1) == digit) then
                result = number(:i-1) // number(i+d:)
                exit
            end if
        end do

    end subroutine solve

end program main
❌ Compiled
❌ Executed
❌ Correct 
module MaximumValueAfterRemovingDigit
    implicit none
    private
    public :: maximumValueAfterRemovingDigit
contains
    function maximumValueAfterRemovingDigit(number, digit) result(result)
        implicit none
        character(len=*), intent(in) :: number
        character(len=*), intent(in) :: digit
        character(len=len(number)) :: result
        integer :: i, j, k, n, d
        logical :: found

        ! Initialize result to empty string
        result = ""

        ! Find the first occurrence of digit in number
        found = .false.
        do i = 1, len(number)
            if (number(i:i) == digit) then
                found = .true.
                exit
            end if
        end do

        ! If digit is not found in number, return empty string
        if (.not. found) then
            return
        end if

        ! Copy the part of number before the first occurrence of digit
        ! to the result string
        do i = 1, len(number)
            if (i < i - 1) then
                result(i:i) = number(i:i)
            end if
        end do

        ! Remove the first occurrence of digit from the result string
        do i = 1, len(result)
            if (result(i:i) == digit) then
                result(i:i) = ""
                exit
            end if
        end do

        ! Find the maximum value of the resulting string in decimal form
        n = len(result)
        d = 0
        do i = n, 1, -1
            d = d * 10 + ichar(result(i:i)) - ichar("0")
        end do

        ! Return the maximum value
        result = d
    end function maximumValueAfterRemovingDigit
end module MaximumValueAfterRemovingDigit

program test_maximumValueAfterRemovingDigit
    use MaximumValueAfterRemovingDigit
    implicit none
    integer :: i

    do i = 1, size(test_cases)
        write (*,*) "Test case #", i
        write (*,*) "Input: ", test_cases(i)%number, ", ", test_cases(i)%digit
        write (*,*) "Output: ", maximumValueAfterRemovingDigit(test_cases(i)%number, test_cases(i)%digit)
        write (*,*)
    end do

contains
    type TestCase
        character(len=100) :: number
        character(len=100) :: digit
    end type TestCase

    type(TestCase), parameter :: test_cases(*) = &
        (/TestCase("123 ", "3 "), &
        TestCase("1231 ", "1 "), &
        TestCase("551 ", "5 ")/)
end program test_maximumValueAfterRemovingDigit
🌐 Data from online sources 
def max_number_after_remove_digit(number: str, digit: str) -> str:
    index = number.find(digit)
    return number[:index] + number[index + 1:]

The algorithm for all the implementations is as follows:

  1. Find the index of the first occurrence of the digit in the number string.
  2. Make a copy of the number string (this is done implicitly for Java, Python, and JavaScript when manipulating strings), removing the digit at the found index.
  3. Return the new string as the result.

In all language implementations, we first use string methods like find, indexOf, or search to find the index of the first occurrence of the digit in the number string. After that, we create a new string by removing the digit at that index using different string methods like erase (in C++), substring (in Java), string slicing (in Python), or slice method (in JavaScript).

The time complexity for this algorithm is O(n) where n is the length of the number string. This is because finding the index of the digit and removing the digit from the string takes linear time.

🌐 Data from online sources 
std::string maxNumberAfterRemoveDigit(const std::string& number, const char digit) {
    size_t index = number.find(digit);
    std::string result = number;
    result.erase(index, 1);
    return result;
}

The algorithm for all the implementations is as follows:

  1. Find the index of the first occurrence of the digit in the number string.
  2. Make a copy of the number string (this is done implicitly for Java, Python, and JavaScript when manipulating strings), removing the digit at the found index.
  3. Return the new string as the result.

In all language implementations, we first use string methods like find, indexOf, or search to find the index of the first occurrence of the digit in the number string. After that, we create a new string by removing the digit at that index using different string methods like erase (in C++), substring (in Java), string slicing (in Python), or slice method (in JavaScript).

The time complexity for this algorithm is O(n) where n is the length of the number string. This is because finding the index of the digit and removing the digit from the string takes linear time.