LeetCode 1903. Largest Odd Number in String

Description

https://leetcode.com/problems/largest-odd-number-in-string/

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.

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

Check the string from backwards, if find an odd character, that is the largest odd number.

Python Solution

class Solution:
    def largestOddNumber(self, num: str) -> str:
        
        for i in range(len(num) - 1, -1, -1):            
            c = num[i]
            
            if int(c) % 2 != 0:
                return num[:i + 1]
        
        return ""
  • Time Complexity: O(N).
  • Space Complexity: O(1).

Leave a Reply

Your email address will not be published.