Largest Odd Number in String LeetCode

Key takeaways:

• A substring is defined as a continuous sequence of characters within the string.

• If no odd number exists, the output should be an empty string.

• The algorithm iterates through the string from the end, checking for odd numbers.

• The substring is returned up to and including the found odd number.

• If no odd number is found during the iteration, an empty string is returned.

• Example inputs and outputs include “354” returning “35” and “7634” returning “763.”

• The time complexity of the algorithm is $O(n)$, and the space complexity is $O(1)$.

Finding the Largest Odd Number in a string involves locating the largest odd number within a string that comprises only digits. Solving this LeetCode problem will enhance our skills in string manipulation and algorithm design. For instance, given a string “574839,” the largest odd number that can be formed is “839.” Another example is the string “2468,” where no odd number can be found, resulting in an empty output.

Problem statement

In this problem, a substring is defined as a continuous sequence of characters within a string. Given a string number that represents a number, our task is to return the largest odd substring within this string. If no odd substring is present, we have to return an empty string ("").

Constraints:

• 1 <= number.length <= 103

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

The table below shows some sample inputs and their expected outputs:

Knowledge test

Attempt the quiz below to test your concepts on this problem:

An algorithm to find the largest odd number

Here are the steps for this problem:

• Iterate through the characters of num, starting from the last character.

• In each loop, check if it’s an odd number. If it is, return a substring from the beginning (current index i of the loop) up to and including the current character (num[:i + 1]).

• After iterating through the string, if no odd number was found, return "".

An example of this problem is provided in the slides below:

Code to find the largest odd number

The code solution to this problem is provided below:

Code explanation

This code can be explained below:

• Line 1: Define a function oddnumber, which takes the string num as a parameter.

• Line 2: Iterate through the string, starting from the last character of the string and progressing backward. We do this as the last character will decide whether the number is odd or even.

• Line 3: Check if the number is odd.

• Line 4: If an odd number is found, return the entire string until that index. This is because, regardless of the preceding digits, if the last digit is odd, the entire number is also odd.

• Lines 7–13: Find the largest odd number in a string by calling the oddnumber function.

You may alter the code at the end to test with your values.

Time complexity

The time complexity of the oddnumber function is $O(n)$, where $n$ is the length of the input string num.

Space complexity

Since the space used by the function remains constant regardless of the size of the input string num, the space complexity of the oddnumber function is $O(1)$.