Teaching Kids Programming – Largest Odd Number in String

Teaching Kids Programming: Videos on Data Structures and Algorithms

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 &lt= 10^5
num only consists of digits and does not contain any leading zeros.

Hints:
In what order should you iterate through the digits?
If an odd number exists, where must the number start from?

Greedy Algorithm to Find Largest Odd Number in String

The largest number can be made by constructing the chunck up to the rightmost odd digit. Therefore, we need to scan from the right towards to the left and stop and return the chunk up to it.

1
2
3
4
5
6

class Solution:
    def largestOddNumber(self, num: str) -> str:
        for i in range(len(num) - 1, -1, -1):
            if (int(num[i]) & 1) == 1:
                return num[:i+1]
        return ""

class Solution:
    def largestOddNumber(self, num: str) -> str:
        for i in range(len(num) - 1, -1, -1):
            if (int(num[i]) & 1) == 1:
                return num[:i+1]
        return ""

If there is no odd numbers, there is no odd numbers, and hence return empty string. The time complexity is O(N) where N is the length of the string. The space complexity is O(1), as we don’t need to use additional space.

–EOF (The Ultimate Computing & Technology Blog) —