Jobs

Interviews

Discussions

Largest Odd Number in String

Easy

Asked by:

More companies

19 views

Topics:

Strings

You are given a string num, representing a large integer. Return the largest-valued odd integer (as a string) that is a non-empty substring of num, or an empty string "" if no odd integer exists.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: num = "52"
Output: "5"
Explanation: The only non-empty substrings are "5", "2", and "52". "5" is the only odd number.

Example 2:

Input: num = "4206"
Output: ""
Explanation: There are no odd numbers in "4206".

Example 3:

Input: num = "35427"
Output: "35427"
Explanation: "35427" is already an odd number.

Constraints:

1 <= num.length <= 10⁵
num only consists of digits and does not contain any leading zeros.

Try coding it in LeetCode

Largest Odd Number in String

Easy

Asked by:

19 views

Topics:

Strings

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: num = "52"
Output: "5"
Explanation: The only non-empty substrings are "5", "2", and "52". "5" is the only odd number.

Example 2:

Input: num = "4206"
Output: ""
Explanation: There are no odd numbers in "4206".

Example 3:

Input: num = "35427"
Output: "35427"
Explanation: "35427" is already an odd number.

Constraints:

1 <= num.length <= 10⁵
num only consists of digits and does not contain any leading zeros.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string `num`?
Can the input string `num` be empty or null?
Is the input string `num` guaranteed to contain only digits?
If there are multiple odd number substrings with the same length, should I return the one that appears first?
If no odd number substring exists, should I return an empty string or null?

Brute Force Solution

Approach

We need to find the biggest odd number that can be formed from the ending part of a given number, which is represented as a string. The brute force method will try all possible ending parts of the number, one by one, to see if any of them are odd.

Here's how the algorithm would work step-by-step:

Start by looking at the entire number as a possible answer.
Check if the entire number is odd. If it is, we've found our answer.
If the entire number is not odd, remove the last digit and look at the remaining part of the number.
Check if this shorter number is odd. If it is, we've found our answer.
Keep removing the last digit, one at a time, and checking if the remaining part of the number is odd.
Continue this process until there are no digits left.
If we never found an odd number along the way, it means there's no odd number in the string, so the answer is nothing.

Code Implementation

def largest_odd_number_in_string(number):
    # Iterate from the full number down to single digits
    for substring_length in range(len(number), 0, -1):
        possible_odd_number = number[:substring_length]

        # Check if the current substring is odd

        if int(possible_odd_number) % 2 != 0:
            return possible_odd_number

        # If no odd number is found, return an empty string

    return ""

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string 'num' from right to left. In the worst-case scenario, it examines each digit of the string once, stopping when it encounters an odd digit. The number of iterations is directly proportional to the length of the string, 'n'. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The provided algorithm iterates through the string by shortening it in each step, but it doesn't create any new data structures. It operates directly on the input string without making copies or storing intermediate results in auxiliary memory. The only extra space used is for a few scalar variables for iteration, which takes up constant space regardless of the input string's length (N). Therefore, the space complexity is O(1).

Optimal Solution

Approach

To find the largest odd number within a string of digits, we want to avoid unnecessary work. The key idea is that an odd number must end in an odd digit, and we want the longest possible odd number, so we start from the end and work backwards.

Here's how the algorithm would work step-by-step:

Begin at the rightmost digit of the string.
Check if the current digit is odd.
If the digit is odd, we've found the largest odd number, which is the substring from the beginning of the string up to and including this odd digit.
If the digit is even, move one position to the left.
Repeat the process of checking the digit and moving left until you find an odd digit or you reach the beginning of the string.
If you reach the beginning of the string without finding an odd digit, it means there is no odd number within the string, so return an empty string.

Code Implementation

def largestOddNumber(number):
    for index in range(len(number) - 1, -1, -1):
        # Start from the end to find the rightmost odd digit.
        current_digit = int(number[index])

        if current_digit % 2 != 0:
            # If odd, return the substring up to and including this digit.
            return number[:index+1]

    # No odd digit found, so return an empty string.
    return ""

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string 'num' of length 'n' at most once, starting from the end and moving towards the beginning. In each iteration, it performs a constant-time check to determine if the current digit is odd. The loop terminates as soon as an odd digit is found or the beginning of the string is reached. Therefore, the time complexity is directly proportional to the length of the string, resulting in O(n).

Space Complexity

O(1) – The algorithm iterates through the input string `num` without creating any auxiliary data structures like arrays, lists, or hash maps. It only uses a constant amount of extra space to store variables for indexing and potentially one for the result, independent of the input string's length. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Empty input string	Return empty string as specified in the problem when no odd number exists.
Input string containing only even digits	Return empty string since no odd substring can be formed.
Input string with a single odd digit	Return the input string itself as it's the largest odd number.
Very large input string (close to maximum allowed string length)	Iterate from the end of the string; this avoids unnecessary substring creation and scales linearly.
Input string starts with leading zeros followed by an odd number	The substring starting from the first odd digit will be the largest odd number; leading zeros are irrelevant since we are finding the largest value, not numerical value.
Input string ends with an odd number	The entire input string is the largest odd number.
Input string contains mixture of leading/trailing even digits and only one odd number	Iterating from the end and removing even digits ensures finding the largest odd substring quickly.
Input string consists of only the character '0'	Return an empty string as '0' is not odd.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string `num`?
Can the input string `num` be empty or null?
Is the input string `num` guaranteed to contain only digits?
If there are multiple odd number substrings with the same length, should I return the one that appears first?
If no odd number substring exists, should I return an empty string or null?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the entire number as a possible answer.
Check if the entire number is odd. If it is, we've found our answer.
If the entire number is not odd, remove the last digit and look at the remaining part of the number.
Check if this shorter number is odd. If it is, we've found our answer.
Keep removing the last digit, one at a time, and checking if the remaining part of the number is odd.
Continue this process until there are no digits left.
If we never found an odd number along the way, it means there's no odd number in the string, so the answer is nothing.

Code Implementation

def largest_odd_number_in_string(number):
    # Iterate from the full number down to single digits
    for substring_length in range(len(number), 0, -1):
        possible_odd_number = number[:substring_length]

        # Check if the current substring is odd

        if int(possible_odd_number) % 2 != 0:
            return possible_odd_number

        # If no odd number is found, return an empty string

    return ""

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Begin at the rightmost digit of the string.
Check if the current digit is odd.
If the digit is odd, we've found the largest odd number, which is the substring from the beginning of the string up to and including this odd digit.
If the digit is even, move one position to the left.
Repeat the process of checking the digit and moving left until you find an odd digit or you reach the beginning of the string.
If you reach the beginning of the string without finding an odd digit, it means there is no odd number within the string, so return an empty string.

Code Implementation

def largestOddNumber(number):
    for index in range(len(number) - 1, -1, -1):
        # Start from the end to find the rightmost odd digit.
        current_digit = int(number[index])

        if current_digit % 2 != 0:
            # If odd, return the substring up to and including this digit.
            return number[:index+1]

    # No odd digit found, so return an empty string.
    return ""

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input string	Return empty string as specified in the problem when no odd number exists.
Input string containing only even digits	Return empty string since no odd substring can be formed.
Input string with a single odd digit	Return the input string itself as it's the largest odd number.
Very large input string (close to maximum allowed string length)	Iterate from the end of the string; this avoids unnecessary substring creation and scales linearly.
Input string starts with leading zeros followed by an odd number	The substring starting from the first odd digit will be the largest odd number; leading zeros are irrelevant since we are finding the largest value, not numerical value.
Input string ends with an odd number	The entire input string is the largest odd number.
Input string contains mixture of leading/trailing even digits and only one odd number	Iterating from the end and removing even digits ensures finding the largest odd substring quickly.
Input string consists of only the character '0'	Return an empty string as '0' is not odd.