Problem

You are given a string num, representing a large integer. Return the largest-valued odd integer (as a string) that is a non-empty substring of num, or an empty string "" if no odd integer exists.

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

Examples

Example 1:

1
2
3

Input: num = "52"
Output: "5"
Explanation: The only non-empty substrings are "5", "2", and "52". "5" is the only odd number.

Example 2:

1
2
3

Input: num = "4206"
Output: ""
Explanation: There are no odd numbers in "4206".

Example 3:

1
2
3

Input: num = "35427"
Output: "35427"
Explanation: "35427" is already an odd number.

Solution

Method 1 - Iteration

To find the largest-valued odd integer as a non-empty substring of the given string num, we need to consider the following points:

  1. Odd Numbers:
    • An integer is odd if its last digit is odd. Therefore, we only need to check the last digit of all possible substrings to determine if the substring represents an odd number.
  2. Largest-Valued Substring:
    • Since the problem requires the largest-valued odd integer, we can start from the end of the string. The largest value would be the longest possible substring ending at the current position if it forms an odd integer.
  3. Traversal from the End:
    • By traversing from the end, we can quickly identify the largest and longest substring that forms an odd integer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

public class Solution {
    public String largestOddNumber(String num) {
        for (int i = num.length() - 1; i >= 0; i--) {
            if ((num.charAt(i) - '0') % 2 != 0) {
                return num.substring(0, i + 1);
            }
        }
        return "";
    }
}
1
2
3
4
5
6

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

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string num. We make a single pass through the string.
  • 🧺 Space complexity: O(1) for storing the result, aside from the input and output storage.