Leetcode – Largest Odd Number in String Solution

Spread the love

The “Largest Odd Number in String” problem is a classic example of string manipulation and arithmetic property validation in coding interviews. The problem is tagged as an easy problem on Leetcode, but it packs in it several useful tricks and techniques that are helpful for similar types of problems. This article provides a comprehensive guide to understand and solve this problem efficiently.

1. Problem Statement

You are given a string num, representing a large integer. You need to return the largest odd number represented as a substring of num. If no odd number is found, return an empty string.

2. Approaches

2.1 Naive Method: Iterating from the Start

The naive method is to iterate from the start of the string and try to find the largest odd number by concatenating the digits one by one and checking if the number is odd. This method is simple but inefficient, especially for large inputs.

Python Code:

def largestOddNumber(num):
    ans = ""
    temp = ""
    for digit in num:
        temp += digit
        if int(temp) % 2 == 1:
            ans = temp
    return ans

2.2 Optimized Method: Iterating from the End

The optimized method would be to iterate from the end of the string. The advantage here is that as soon as we encounter an odd digit, we can be sure that we have found the largest odd number.

Python Code:

def largestOddNumber(num):
    for i in range(len(num) - 1, -1, -1):
        if int(num[i]) % 2 == 1:
            return num[:i+1]
    return ""

3. Complexity Analysis

Naive Method:

  • Time Complexity: O(n^2) due to string concatenation in a loop.
  • Space Complexity: O(n)

Optimized Method:

  • Time Complexity: O(n), where n is the length of the string.
  • Space Complexity: O(1)

4. Conclusion

This problem serves as a good practice for manipulating and iterating through strings and also adds the challenge of considering numerical properties like odd and even numbers. Once you grasp the idea behind finding the largest odd number, the coding part becomes straightforward. It’s an excellent problem for beginners to get familiarized with string manipulation techniques in Python.

Leave a Reply