💬 Discord
Sign In
NeetCode #887LC-1903EasyMath & Geometry
← Back to All Problems

#887 · #1903 · Largest Odd Number in String(字符串中的最大奇数)

📌 Problem Statement & Constraints

Given a string num representing a large integer, return the largest-valued odd integer that is a prefix of num, or an empty string if no odd prefix exists. Constraints: 1 <= num.length <= 10^5, num contains only digits and has no leading zeros.

💡 Core Algorithmic Approaches

  1. The parity of an integer is determined solely by its last digit, so a prefix is odd exactly when its last digit is odd.
  2. Scan num from the right and stop at the first odd digit.
  3. The prefix up to and including that digit is the longest odd prefix, hence the largest-valued one.
  4. If no odd digit exists, return an empty string.

💻 Benchmark Python3 Implementation

class Solution:
    def largestOddNumber(self, num: str) -> str:
        for i in range(len(num) - 1, -1, -1):
            if int(num[i]) % 2 == 1:
                return num[:i + 1]     # longest odd prefix
        return str()

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): at most one backward scan.
💾 Space Complexity
O(1) beyond the returned slice.

⚠️ Interview Pitfalls & Follow-ups

  • Scanning from the left: the first odd digit found there gives the shortest prefix, not the largest.
  • Stripping only the trailing even digit: the scan must continue until an odd digit is reached, since the new last digit may also be even.
  • Converting the whole string to an integer: unnecessary and possibly overflowing in fixed-width languages.
  • Returning a zero character instead of an empty string: when no odd prefix exists, the required result is the empty string.