1903. Largest Odd Number in String - Explanation

Problem Link



1. Brute Force

class Solution:
    def largestOddNumber(self, num: str) -> str:
        res = ""
        for i in range(len(num)):
            for j in range(i, len(num)):
                ones_digit = ord(num[j]) - ord('0')
                if ones_digit & 1:
                    cur = num[i:j + 1]
                    if len(res) < len(cur) or (len(cur) == len(res) and res < cur):
                        res = cur
        return res

Time & Space Complexity

  • Time complexity: O(n3)O(n ^ 3)
  • Space complexity: O(n)O(n)

2. Find The Rightmost Odd Digit

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

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity:
    • O(1)O(1) extra space.
    • O(n)O(n) for the output string.