easy Largest Odd Number in String

Problem Statement

Given a large integer num represented as string, return the largest-valued odd integer (represented as a string) that is a non-empty substring of num. If no such number exists, the result should be an empty string.

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

Examples

• Example 1:

  • Input: num = "238946"
  • Expected Output: "2389"
  • Justification: The largest odd number in the string is "2389".

• Example 2:

  • Input: num = "2804"
  • Expected Output: ""
  • Justification: Since there are no odd numbers in the input string, the output is an empty string.

• Example 3:

  • Input: num = "13579"
  • Expected Output: "13579"
  • Justification: The entire input string is the largest odd number itself, as all digits are odd.

Solution

To solve this problem, we'll iterate through the string from right to left, searching for the first odd digit. Odd digits make a number odd, so finding any such digit means the substring up to and including that digit is the largest odd number we can form.

This approach works because trimming any digits to the right of the found odd digit will not affect the oddness of the number, and since we're scanning from right to left, we ensure the largest possible odd number is found. This method is efficient because it requires only a single pass through the string, making it optimal for both time and space complexity.

Step-by-step Algorithm

• Start by checking if the input string is empty. If yes, return an empty string immediately.
• Iterate through the string from the last character to the first:
  • For each character, check if it is an odd digit (1, 3, 5, 7, or 9).
    • If an odd digit is found, return the substring from the start of the string to this digit's index (inclusive).
• If no odd digit is found by the end of the iteration, return an empty string, indicating no odd number can be formed.

Algorithm Walkthrough

Given input: "238946"

• Start from the last digit ("6") and move leftward.
• 6 is even, move to 4.
• 4 is even, move to 9.
• 9 is odd, so we take the substring from the start to this digit, which gives "2389".
• Return "2389" as the largest odd number that can be formed.

Code

public class Solution {

  // Method to find the largest odd number in string
  public String largestOddNumber(String num) {
    // Iterate from the end of the string towards the beginning
    for (int i = num.length() - 1; i >= 0; i--) {
      // Check if the current digit is odd
      if ((num.charAt(i) - '0') % 2 != 0) {
        // Return the substring from start to the current odd digit
        return num.substring(0, i + 1);
      }
    }
    // Return an empty string if no odd digit is found
    return "";
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Test the method with example inputs
    System.out.println(solution.largestOddNumber("238946")); // "2389"
    System.out.println(solution.largestOddNumber("5804")); // "5"
    System.out.println(solution.largestOddNumber("13579")); // "13579"
  }
}

Complexity Analysis

Time Complexity

The time complexity for the algorithm in all provided languages is , where n is the length of the input string. This is because, in the worst case, the algorithm scans through the entire string once to find the first odd digit from the right.

Space Complexity

The space complexity is . The algorithm uses a fixed amount of space to store intermediate variables, regardless of the input size.