algoadvance

Leetcode 1903. Largest Odd Number in String

Problem Statement

Given a string num, which represents a large integer, return the largest-valued odd number (as a substring) that is actually a contiguous substring of num. If no odd number exists, return an empty string “”.

Clarifying Questions

1. Input Constraints:
   • Is the input string guaranteed to contain only digits?
   • Can the input string be empty?
2. Output Specifications:
   • Do we need to handle large strings efficiently?
   • Are there additional constraints on the size of the input string?

Based on common problem setups, it is usually safe to assume:

• The input string num contains only digits and may be empty.
• The solution should be capable of handling large strings, potentially up to a length of 10^6.

Strategy

To find the largest odd number as a contiguous substring:

1. Iterate over the string from the end to the beginning until you find an odd digit.
2. As soon as you find an odd digit, return the substring from the start of the string to this odd digit (inclusive).

This approach is efficient since you only need to traverse the string once from the end to the start.

Time Complexity

• Time Complexity: O(n), where n is the length of the input string. This is because we might need to traverse the entire string in the worst case.
• Space Complexity: O(1), since no additional space besides a few variables is required.

Code

public class Solution {
    public String largestOddNumber(String num) {
        // Iterate from the end to the beginning to find the first odd digit
        for (int i = num.length() - 1; i >= 0; i--) {
            char c = num.charAt(i);
            if ((c - '0') % 2 != 0) {
                // Return the substring up to and including this odd digit
                return num.substring(0, i + 1);
            }
        }
        // If no odd digit is found, return an empty string
        return "";
    }

    // Main function for quick testing
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.largestOddNumber("52")); // "5"
        System.out.println(solution.largestOddNumber("4206")); // ""
        System.out.println(solution.largestOddNumber("35427")); // "35427"
    }
}

Explanation of the Code

1. We define the method largestOddNumber which takes a string num as input.
2. We loop through the string from the last character to the first.
3. For each character, we check if it represents an odd digit by converting it to an integer and checking if it is not divisible by 2.
4. If we find an odd digit, we return the substring from the start of num to this position.
5. If no odd digit is found, we return an empty string.

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?