algoadvance

Leetcode 2259. Remove Digit From Number to Maximize Result

Problem Statement

You are given a string number representing a positive integer and a character digit. You need to remove one occurrence of digit from number so that the resulting string is the largest possible integer. Return the resulting string as an integer in string format.

Example:

Input: number = "1231", digit = '1'
Output: "231"

Input: number = "551", digit = '5'
Output: "51"

Input: number = "123", digit = '3'
Output: "12"

Clarifying Questions

1. Can there be multiple occurrences of digit in the number?
   • Yes, but we need to remove only one occurrence to get the largest possible number.
2. Can the input number contain leading zeros after removing the digit?
   • The problem guarantees that number is a valid positive integer, so there won’t be leading zeros.
3. What should be done if removing any digit does not increase the number?
   • Even if the number decreases, we need to remove one occurrence of the specified digit.

Strategy

1. Iterate through the number:
   • Iterate through each character in the string number.
2. Find Potential Candidates:
   • Whenever we encounter the digit, consider the number formed by removing the current occurrence of digit.
3. Determine the Maximum Possible Result:
   • Track each possible number formed by removing one occurrence of digit and determine the maximum of these numbers.
4. Implementation Details:
   • Use a variable to store the maximum of these possible numbers as we iterate through the string.

Code

public class Solution {
    public String removeDigit(String number, char digit) {
        String maxNumber = "";
        int length = number.length();

        for (int i = 0; i < length; i++) {
            if (number.charAt(i) == digit) {
                String candidate = number.substring(0, i) + number.substring(i + 1);
                if (maxNumber.isEmpty() || candidate.compareTo(maxNumber) > 0) {
                    maxNumber = candidate;
                }
            }
        }

        return maxNumber;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.removeDigit("1231", '1')); // Output: "231"
        System.out.println(sol.removeDigit("551", '5'));  // Output: "51"
        System.out.println(sol.removeDigit("123", '3'));  // Output: "12"
    }
}

Time Complexity

• Time Complexity: O(n)
  • We iterate through the string number of length n once, performing substring operations which are O(n) in total. Thus, the overall time complexity is O(n).
• Space Complexity: O(n)
  • We are storing intermediate strings that are formed by removing one occurrence of digit. Hence, the space complexity is also O(n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?