Introduction

In this blog post, we will explore how to solve the LeetCode problem "1903" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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 <= 105 num only consists of digits and does not contain any leading zeros.

Explanation

Here's the breakdown of the solution:

• Right-to-Left Scan: Iterate through the string num from right to left. This allows us to find the largest odd number substring quickly.
• Odd Digit Found: If an odd digit is encountered, the substring from the beginning of num up to and including that odd digit is the largest odd substring.

• No Odd Digit: If the loop completes without finding an odd digit, it means no odd substring exists, so return an empty string.

• Runtime Complexity: O(n), where n is the length of the input string num.

• Storage Complexity: O(1) - constant extra space.

Code

    def largestOddNumber(num: str) -> str:
    """
    Finds the largest-valued odd integer that is a non-empty substring of num.

    Args:
        num: A string representing a large integer.

    Returns:
        The largest odd integer substring, or an empty string if none exists.
    """
    for i in range(len(num) - 1, -1, -1):
        if int(num[i]) % 2 != 0:
            return num[:i + 1]
    return ""