Leetcode 1903: Largest Odd Number in String

Input: A string `num` representing a large integer.

Example: num = "54321"

Constraints:

• 1 <= num.length <= 10^5

• num only consists of digits and does not contain any leading zeros.

Output: Return the largest odd integer (as a string) formed from any non-empty substring of `num`, or an empty string if no odd integer exists.

Example: "54321"

Constraints:

• The output is a string that represents the largest odd number, or an empty string if no odd integer is found.

Goal: Find the largest odd integer from any non-empty substring.

Steps:

• Start by iterating from the end of the string `num`.

• For each digit, check if it is odd.

• If an odd digit is found, return the substring from the beginning of `num` to the current index.

Goal: The input is a string consisting only of digits, with no leading zeros, and the length is between 1 and 10^5.

Steps:

• 1 <= num.length <= 10^5

• num contains only digits and no leading zeros.

Assumptions:

• The string `num` is valid and follows the constraints provided.

• The string will always contain digits.

• Input: Input: num = "54321"

• Explanation: The string '54321' is already an odd number, so it is the largest odd integer possible.

Approach: We can find the largest odd integer by starting from the end of the string `num` and checking each character for oddness. As soon as we find an odd digit, we return the substring from the start to that position.

Observations:

• The problem requires identifying odd integers in substrings efficiently.

• By iterating backward and checking the digits for oddness, we minimize unnecessary checks and ensure an optimal solution.

Steps:

• Iterate from the last character of the string `num`.

• Check if the current digit is odd.

• If an odd digit is found, return the substring from the start to that index.

• If no odd digits are found, return an empty string.

Empty Inputs:

• The input string cannot be empty according to the constraints.

Large Inputs:

• The function should efficiently handle large inputs up to 10^5 digits.

Special Values:

• Handle cases where there are no odd digits in the entire string.

Constraints:

• The string only contains digits, and there are no leading zeros.

string largestOddNumber(string num) {
    string res = "";
    for(int i = num.size(); i >= 0; i--) {
        if((num[i] - '0') % 2)
          return num.substr(0, i + 1);
    }
    return string();
}

1 : Function Definition

string largestOddNumber(string num) {

The function definition starts here. It takes a string `num` and will return the largest odd number formed from the digits in the string.

2 : Variable Initialization

    string res = "";

A string variable `res` is initialized to store the result, although it is not used in this solution.

3 : For Loop

    for(int i = num.size(); i >= 0; i--) {

This for loop iterates backwards through the digits of the string `num` from the last character to the first.

4 : Condition Check

        if((num[i] - '0') % 2)

This condition checks if the current digit is odd by converting the character to an integer and checking if it is divisible by 2.

5 : Return Substring

          return num.substr(0, i + 1);

If the digit is odd, the function returns the substring from the start of `num` to the current position `i`, which forms the largest odd number.

6 : Return Empty String

    return string();

If no odd digit is found, an empty string is returned.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is linear since we are checking each digit of the string once.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is constant since we only use a few variables for processing.

Leetcode 1903: Largest Odd Number in String

Explore →