Largest Odd Number in String
EasyPrompt
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.
Example 1:
Input: num = "52"
Output: "5"
Explanation: The only non-empty substrings are "5", "2", and "52". "5" is the only odd number.Example 2:
Input: num = "4206"
Output: ""
Explanation: There are no odd numbers in "4206".Example 3:
Input: num = "35427"
Output: "35427"
Explanation: "35427" is already an odd number.
Constraints:
1 <= num.length <= 105numonly consists of digits and does not contain any leading zeros.
Approaches
2 approaches with complexity analysis and trade-offs.
The most straightforward approach is to exhaustively check every possible substring of the input string num. For each substring, we determine if it represents an odd number. We then keep track of the largest odd number found throughout this process.
Algorithm
- Initialize a string variable
maxOddto an empty string"". - Use a nested loop to generate all possible substrings of
num. The outer loopidetermines the start index, and the inner loopjdetermines the end index. - For each substring, check if it represents an odd number by examining its last character (
num.charAt(j)). - If the substring is odd, compare it with
maxOdd. A number is larger if its string representation is longer. If lengths are equal, perform a lexicographical comparison. - If the current odd substring is larger than
maxOdd, updatemaxOdd. - After iterating through all substrings, return
maxOdd.
Walkthrough
This method systematically generates all contiguous subsequences of the input string num. For each generated substring, we perform two main checks:
-
Odd Number Check: A number is odd if and only if its last digit is odd. We can quickly check this by looking at the last character of the substring. If it's '1', '3', '5', '7', or '9', the number is odd.
-
Magnitude Comparison: If the substring is odd, we must compare it with the largest odd substring found so far. Since the numbers can be too large for standard integer types like
long, this comparison must be done on their string representations. A longer number string always represents a larger value. If two number strings have the same length, the one that is lexicographically greater is the larger number.
We start with an empty string as our maximum and update it whenever we find a larger odd substring.
class Solution { public String largestOddNumber(String num) { String maxOdd = ""; int n = num.length(); for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { char lastChar = num.charAt(j); // Check if the number ending at index j is odd if ((lastChar - '0') % 2 != 0) { String currentSub = num.substring(i, j + 1); // Compare with the largest odd number found so far if (isLarger(currentSub, maxOdd)) { maxOdd = currentSub; } } } } return maxOdd; } // Helper function to compare two number strings private boolean isLarger(String s1, String s2) { if (s2.isEmpty()) { return true; } if (s1.length() > s2.length()) { return true; } if (s1.length() < s2.length()) { return false; } return s1.compareTo(s2) > 0; }}Complexity
Time
O(N^3). There are O(N^2) possible substrings. For each substring, creation (`substring` method) and comparison can take up to O(N) time, leading to a cubic complexity.
Space
O(N), where N is the length of the input string. This space is used to store the current substring and the largest odd substring found.
Trade-offs
Pros
Simple to conceptualize and implement.
Directly translates the problem statement into code.
Cons
Extremely inefficient with a cubic time complexity, making it impractical for the given constraints.
Will likely result in a 'Time Limit Exceeded' error on most platforms.
A highly efficient solution can be derived from a key insight: to get the largest possible number, we want the longest possible string. A number is odd if its last digit is odd. Therefore, the largest-valued odd substring must be the longest prefix of the original string that ends with an odd digit. This simplifies the problem to finding the rightmost odd digit.
Algorithm
- Iterate through the input string
numfrom right to left, starting from the last character at indexn-1. - In each iteration, get the character and check if its numeric value is odd.
- If an odd digit is found at index
i, it means we have found the rightmost odd digit. - The largest odd number must be the prefix of the string ending at this index. Return the substring from the beginning up to this index (inclusive), i.e.,
num.substring(0, i + 1). - If the loop completes without finding any odd digits, it implies that no odd number can be formed. In this case, return an empty string
"".
Walkthrough
The core idea is that any odd number must end in an odd digit. To maximize the value of the number, we should maximize its length. Let's say the rightmost odd digit in num is at index k.
The prefix P = num.substring(0, k + 1) is an odd number. Now, consider any other odd substring S = num.substring(i, j + 1). For S to be odd, num.charAt(j) must be an odd digit. Since k is the index of the rightmost odd digit, it must be that j <= k.
- If
j < k, thenSis shorter thanP, soPis a larger number. - If
j = k, thenSis a suffix ofP(i.e.,S = num.substring(i, k+1)wherei >= 0). Since the problem states no leading zeros, the full prefixPis always greater than or equal to any of its suffixesS.
Thus, the largest odd number is simply the prefix ending at the rightmost odd digit. Our algorithm is to find this digit by scanning from the right and then return the corresponding prefix.
class Solution { public String largestOddNumber(String num) { for (int i = num.length() - 1; i >= 0; i--) { // Get the numeric value of the character int digit = num.charAt(i) - '0'; // Check if the digit is odd if (digit % 2 != 0) { // Found the rightmost odd digit. // The largest odd number is the prefix ending at this digit. return num.substring(0, i + 1); } } // No odd digit was found in the entire string return ""; }}Complexity
Time
O(N), where N is the length of the string. In the worst-case scenario, we traverse the entire string once. The substring operation is called at most once.
Space
O(1) auxiliary space. The space for the returned substring can be up to O(N), but this is typically not counted as auxiliary space.
Trade-offs
Pros
Extremely efficient with linear time complexity.
Simple and concise implementation.
Optimal solution for the given constraints.
Cons
The logic relies on a key insight that might not be immediately obvious.
Solutions
Solution
class Solution {public String largestOddNumber(String num) { for (int i = num.length() - 1; i >= 0; --i) { int c = num.charAt(i) - '0'; if ((c & 1) == 1) { return num.substring(0, i + 1); } } return ""; }}/** * @param {string} num * @return {string} */ var largestOddNumber = function (num) { for (let i = num.length - 1; ~i; --i) { if (Number(num[i]) & 1) { return num.slice(0, i + 1); } } return ""; };class Solution {public: string largestOddNumber(string num) { for (int i = num.size() - 1; i >= 0; --i) { int c = num[i] - '0'; if ((c & 1) == 1) { return num.substr(0, i + 1); } } return ""; }};class Solution : def largestOddNumber ( self , num : str ) -> str : for i in range ( len ( num ) - 1 , - 1 , - 1 ): if ( int ( num [ i ]) & 1 ) == 1 : return num [: i + 1 ] return ''Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.