algoadvance

Leetcode 1903. Largest Odd Number in String

Problem Statement

You are given a string num, which represents a large integer. Return the largest-valued odd number that is a non-empty substring of num, or an empty string “” if no odd number exists.

A substring is a contiguous sequence of characters within a string.

Clarifying Questions

1. Input length: What is the maximum length of the string num?
   • Typically, the constraints will be mentioned in the problem. For LeetCode problems, this could typically go up to 10^5 or more.
2. Character composition: Can num contain any non-numeric characters?
   • No, num only contains numeric digits from ‘0’ to ‘9’.
3. Empty string: What should be the output if input num is an empty string?
   • Return an empty string “”.

Strategy

To solve this problem effectively, you can follow these steps:

1. Identify Odd Numbers: Remember that a number ends in an odd digit if and only if its last digit is odd (‘1’, ‘3’, ‘5’, ‘7’, ‘9’).
2. Search from the End: Traverse the string from the end to the beginning to find the last odd digit. This is because the largest odd number will be the prefix up to and including this last odd digit.
3. Return the Result: Once an odd digit is found, return the substring from the beginning to this digit (inclusive).

Code

#include <string>

class Solution {
public:
    std::string largestOddNumber(std::string num) {
        int n = num.size();
        for (int i = n - 1; i >= 0; --i) {
            if ((num[i] - '0') % 2 == 1) {
                return num.substr(0, i + 1);
            }
        }
        return "";
    }
};

Explanation

1. String Traversal: Start from the last index of the string and iterate backward.
2. Check for Odd Digit: For each character, convert it to an integer and check if it is odd.
3. Return Substring: When an odd digit is found, return the substring from the start of the string up to and including this digit.
4. If no odd digit is found during the traversal, return an empty string.

Time Complexity

• Time Complexity: The algorithm traverses the string once, so it has a linear time complexity of O(n), where n is the length of the string num.
• Space Complexity: The space complexity is O(1) because we only use a few additional variables and do not require extra space proportional to the input size.

This approach ensures that we efficiently find the largest odd-valued number that can be obtained as a substring of the given string num.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?